##
10 posts tagged with Mathematics *and* complexity.

Displaying 1 through 10 of 10. Subscribe:

## So, the unknowable kicks in

Logic hacking - "Writing shorter and shorter computer programs for which it's unknowable whether these programs run forever, or stop... the winner of the Busy Beaver Game for N-state Turing machines becomes unknowable using ordinary math - somewhere between N = 5 and N = 1919." [more inside]

## 21st Century Wiener

Norbert Wiener: The Eccentric Genius Whose Time May Have Finally Come (Again) - "The most direct reason for Wiener's fall to relative obscurity was the breakthrough of a young mathematician and engineer named Claude Shannon." [more inside]

## A SAT Attack on the Erdos Discrepancy Conjecture

Computers are providing solutions to math problems that we can't check - "A computer has solved the longstanding Erdős discrepancy problem! Trouble is, we have no idea what it's talking about — because the solution, which is as long as all of Wikipedia's pages combined, is far too voluminous for us puny humans to confirm." (via; previously ;)

## John Baez on the maths of connecting everyone (and everything) on earth

Network Theory Overview - "The idea: nature and the world of human technology are full of networks! People like to draw diagrams of networks. Mathematical physicists know that in principle these diagrams can be understood using category theory. But why should physicists have all the fun? This is the century of

*understanding living systems and adapting to life on a finite planet*. Math isn't the main thing we need, but it's got to be part of the solution... so one thing we should do is develop a unified and powerful theory of networks." (via ;)## Computerized Math, Formal Proofs and Alternative Logic

Using computer systems for doing mathematical proofs - "With the proliferation of computer-assisted proofs that are all but impossible to check by hand, Hales thinks computers must become the judge." [more inside]

## direct realism

The Nature of Computation - Intellects Vast and Warm and Sympathetic: "I hand you a network or graph, and ask whether there is a path through the network that crosses each edge exactly once, returning to its starting point. (That is, I ask whether there is a 'Eulerian' cycle.) Then I hand you another network, and ask whether there is a path which visits each node exactly once. (That is, I ask whether there is a 'Hamiltonian' cycle.) How hard is it to answer me?" (via) [more inside]

## from complexity, universality

## Complex matters for the millenium

*I am pleased to announce a proof that P is not equal to NP.*In this paper, Vinay Deolalikar (HP Labs) proposes a proof to answer the most important problem in its field of mathematics. [more inside]

## The Complexity of a Controversial Concept

The Logic of Diversity "A new book,

*The Wisdom of Crowds*[..:] by The New Yorker columnist James Surowiecki, has recently popularized the idea that groups can, in some ways, be smarter than their members, which is superficially similar to Page's results. While Surowiecki gives many examples of what one might call collective cognition, where groups out-perform isolated individuals, he really has only one explanation for this phenomenon, based on one of his examples: jelly beans [...] averaging together many independent, unbiased guesses gives a result that is probably closer to the truth than any one guess. While true — it's the central limit theorem of statistics — it's far from being the only way in which diversity can be beneficial in problem solving." (Three-Toed Sloth)## The Computational Complexity of Air Travel Planning

Do you have problems finding the cheapest flight? Well so do computers.

Carl de Marcken, the man who created the engine behind Orbitz and other travel search engines posits that finding the cheapest fare from one point to another is a NP-Hard problem. Even if you fix the specific route between destinations there can be as many as 10

Carl de Marcken, the man who created the engine behind Orbitz and other travel search engines posits that finding the cheapest fare from one point to another is a NP-Hard problem. Even if you fix the specific route between destinations there can be as many as 10

^{36}combinations.Page:
1