LESSWRONG
is fundraising!
LW
$

Comment Permalink

I can write down a polynomial time algorithm which solves SAT (for all but finitely many instances at least), provided that in fact P = NP. The difficulty is proving that this particular algorithm works, which could easily be true but independent of ZFC.

dlthomas13y10

Elaborate, please.

See in context

1 What independence between ZFC and P vs NP would imply

by Alex Flint

8th Dec 2011

2 min read

1

Suppose we had a model M that we thought described cannons and cannon balls. M consists of a set of mathematical assertions about cannons, and the hypothesis is that these fully describe cannons in the sense that any question about cannons ("what trajectory do cannon balls follow for certain firing angles?", "Which angle should we pick to hit a certain target?") can be answered by deriving statements from M. Suppose further that M is specified in a certain mathematical system called A, consisting of axioms A1...An.

Now there is much to be said about good ways to find out whether M is true of cannons or not, but consider just this particular (strange) outcome: Suppose we discover that a crucial question about cannons - e.g. Q="Do cannon balls always land on the ground, for all firing angles?" - turned out to be not just un-answerable by our model M but formally independent of the mathematical system A in the sense that the addition of some axiom A0 implies Q, while the addition of its negation, ~A0, implies ~Q.

What would this say about our model for cannons? Let's suppose that we can take Q as a prima facie substantive question with a definitive yes or no answer regardless of any model or axiomatization. At the very least it seems that M must be an incomplete model of cannons if the system in which it is specified is insufficient to answer the various questions of interest. It seems to me that

If a question about reality turns out to be logically independent of a model M, then M is not a complete model of reality.

Now we have an axiomatization of mathematics -- let's say it's ZFC for now -- and we have a model of computation in reality, which is M="The unvierse can contain machines that (efficiently) compute F iff there exists a Turing machine that (efficiently) computes F" with appropriate definitions of what exactly a Turing machine is in terms of ZFC. Suppose we want to answer a question like Q="Can the universe contain machines that efficiently solve SAT?"

Under the premise that M is true, the question Q becomes the pure logical question R="Are there Turing machines that efficiently solve SAT?", i.e. the P versus NP problem.

Now suppose that R was shown to be formally independent of ZFC in the sense that for some axiom A0, ZFC+A0 implies P=NP and ZFC+~A implies P!=NP. This would resolve the mathematical question of P versus NP but the question Q seems like a prima facie concrete question with a definitive yes or no answer that does not rely for its substance on M or ZFC or any other epistemic construct. It would seem that we must have missed something in our description of reality, M.

Perhaps more controversially, I claim: Under the correct model M' it seems that it's impossible for a substantive question (such as Q) to be unanswerable.

All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete.

Personal Blog

1

New Comment

63 comments, sorted by

top scoring

Click to highlight new comments since: Today at 5:58 PM

[-]cousin_it13y170

Your post doesn't seem to have anything to do with P vs NP, it's just a statement of indignation at Gödel's incompleteness theorems :-)

Here's a simplified example. Imagine you have an axiomatic "model of reality" that describes computers. Then I can write a computer program that successively generates all valid proofs in that axiom system. If the program stumbles upon a valid proof that 1=0, it halts, otherwise it goes on searching. It seems to be a "prima facie substantive question" whether the program will halt or not, but our axiom system cannot settle it because it cannot prove its own consistency by Gödel's second incompleteness theorem, unless it is inconsistent.

The root of the problem, IMO, is our inability to describe integers. By the Löwenheim–Skolem theorem, you cannot have an axiomatization of the integers that rules out nonstandard integers. I wrote several posts about this.

[-]Alex Flint13y20

Good point, evidently I failed to really internalize Godel. I had dismissed Godel sentences as not questions about reality but your example is compelling.

Interestingly, your post on integers seemed to suggest you were also thinking that since our models of integers fail to live up to expectations we've somehow failed to describe them, but that it might yet be possible to do so.

[-]Alex Flint13y00

A different perspective: Godel doesn't say that there is any particular question about reality that we cannot answer, only that however far into the model-building enterprise we get, there will always be some undecidable propositions, which can be translated into questions about reality with the TM-enumerating-sentences experiment. So if we have a model of reality M and it fails to answer a question about reality Q then there's always hope that we could discover further regularities in reality to amend M so that it answers Q, but there is no hope that we would ever be free of any open questions. Am I correct in thinking that this rules out the possibility of a GUT, at least if a GUT is defined as a model that answers all questions.

[-]cousin_it13y00

Godel doesn't say that there is any particular question about reality that we cannot answer

Of course! It's a theorem about math. There are no theorems about reality.

Am I correct in thinking that this rules out the possibility of a GUT, at least if a GUT is defined as a model that answers all questions.

Yes and no. You can build computers that enumerate proofs even in universes with simple and known physics, like the Game of Life. But to mathematically define something like an infinite Game of Life grid, you need integers, and we don't have a complete axiomatization of those. So you could have a GUT that's completely defined "relative to the integers". I guess most physicists would accept that as a good enough GUT, even though it's incomplete in the Godelian sense.

[-]JoshuaZ13y90

Now suppose that R was shown to be formally independent of ZFC in the sense that for some axiom A0, ZFC+A0 implies P=NP and ZFC+~A implies P!=NP. This would resolve the mathematical question of P versus NP

This is only true if A0 is independent of ZFC. This makes things unnecessarily complicated and obscures how one would usually prove that something is independent. There are a variety of methods of showing that something is independent, but the most common method is to construct two models of the theory, one with the statement and the other with the negation. If both models are contained in your original system then you know that as long as your original system is consistent, your desired statement is independent. A more concrete example that avoids a lot of the subtleties and abstractions is what happened with the parallel postulate in the 19th century. By making slightly other geometries (such as geometries on the surface of a sphere), one could do the exact same process as above.

All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete

I think you may be confusing reality with our models here. Consider for example the possibility that our universe is actually discrete and finite. If that's the case, then a decent model won't answer whether P != NP or not in the abstract sense.

In general, when a specific question is being asked it helps to try to put in the less abstract version and see if anything changes. In this context, what do you think happens if we replace P ! = NP with some more concrete question? Say for example I want to know if 3^^^^^^3 + 1 has an even or odd number of prime factors. This is at least more concrete in that you can specify a specific computation that if you could do it you could then answer this question. I don't know of any easy way to answer this sort of question but it looks really difficult. It may well be that this question is simply unresolvable in our universe because the computational resources to answer it don't exist. But from the perspective of something like ZFC this question is trivial. This suggests to me that there are subtle issues going on here that you aren't quite addressing. P != NP is a particularly tricky question because there are so many options for what could happen that are logically consistent but seem weird (e.g. there's an algorithm that solves 3-SAT in polynomial time but this can't be proven in ZFC. Or the algorithm's correctness can be proven but not a polynomial bound on its run time. Or the run time can be proven but not the correctness of the algorithm. Etc.)

How issues like undecidability and our modeling of reality interact are really tough. It isn't helpful to jump in with them using an example that is itself really abstract.

All of that said, there's an overview by Scott Aaronson on whether P != NP is undecidable that is worth reading(pdf). He does also discuss towards the end some of the issues you are touching on.

[-]Alex Flint13y00

I think you may be confusing reality with our models here.

Yeah my claim was a little ambiguous. I meant to claim that either (1) our current model of reality fails to describe some truths about the universe or (2) P=NP is decidable in our model. [I'm only clarifying the claim, I'm now dubious about whether this it is true.] You're right- I should add (3) P=NP cannot be cast as a question about reality.

[-][anonymous]13y80

The problem (or, according to some posters, one of the problems) with your idea is that the concept of a polynomial-time algorithm is itself a mathematical question and not a question about reality. If I gave you the running times of an algorithm for input sizes from 1 to 3^^^3, this would not tell you whether the algorithm is polynomial. However, it would answer the question as far as reality is concerned, since it's impossible to perform the algorithm on inputs bigger than that (or even remotely close to that size).

For simple algorithms like bubble sort or whatnot, we can look at the algorithm and say, "oh, that's quadratic time" and that lets us make predictions about how long it will take to run (if it takes 10 seconds to sort a 10^9 element array, then it will probably take 1000 seconds to sort a 10^10 element array). But this is not a statement about reality directly -- this is a mathematical statement which describes reality, in this case.

Furthermore, it is impossible to make this sort of statement in general. Just as we can't tell if an arbitrary program halts or not, we cannot in general say if an arbitrary algorithm runs in polynomial time. In fact, I'd bet that one can construct an algorithm such that the question whether the algorithm runs in polynomial time is independent of ZFC. This is not a question of ZFC failing to describe reality, because it's not a question about reality whether the algorithm is polynomial, to begin with.

As for P=NP... there's actually an interesting exercise that I'd expect anyone in a good theoretical CS class to see. Right now, without doing cutting-edge research, I can write down an algorithm for solving 3SAT with the following property: if P=NP, then the algorithm I write down will run in polynomial time (and obviously the converse also holds). Thus, deciding whether P=NP is isomorphic to determining the running time of this algorithm (which has a very simple description!) As I've stated earlier, it would not be too surprising if this question turned out to be independent of ZFC.

Edit: it appears that my last paragraph has been preempted.

Also: upvoted for an interesting question.

[-]Incorrect13y50

Perhaps more controversially, I claim: Under the correct model M' it seems that it's impossible for a substantive question (such as Q) to be unanswerable.

Have you heard of Gödel's incompleteness theorems?

Whether a Turing Machine ever halts is a concrete question with a definite yes or no answer; but, if we could construct an axiomatic system with a recursively enumerable set of theorems such that for each Turing machine a theorem existed stating whether the machine halted or not, then we could build a decider for whether any Turing machine halts.

All this adds up to: The P versus NP problem (and questions like it that can be phrased as definitive questions about reality) must have an answer unless our model of reality is incomplete.

Then all possible models of reality are incomplete.

also see: http://en.wikipedia.org/wiki/David_Hilbert#Formalism

[-]jsteinhardt13y00

Whether a Turing Machine halts after a certain number of steps has a definite answer. But whether it halts eventually does not necessarily; what empirical data could prove that it halts eventually, other than seeing it halt?

[-]dlthomas13y00

An observation of a loop, a portion of the tape encoding a value that's decreasing each loop, and a check for it falling below a threshold that would lead to a halt?

[-]gwern13y20

That would only work for some turing machines. Incidentally, it's perfectly possible to decide for particular finite turing machines whether it halts - basically either set a time-out equivalent to the Busy Beaver for that TM (and it either halts before, or blows the time-out in which case it never halts), or, IIRC, you can store every configuration of the tape it passes through and if it repeats any configuration, then it will not halt. Neither of these is especially useful.

[-]dlthomas13y20

That would only work for some turing machines.

Of course. I made no claim at having solved the halting problem. My response was specifically to,

what empirical data could prove that it halts eventually, other than seeing it halt?

There is nothing else that will reliably show this for all machines. There are absolutely things that will show this for some machines.

[-]Incorrect13y20

Those heuristics and any others you come up with will fail to tractably confirm whether some machines halt.

[-]dlthomas13y40

Yes, but they can confirm that some machines will halt, without observing that they have halted, which seemed to be what was asked for. Any such approach must of course say "I don't know" (or itself fail to halt) in some cases.

[-]jsteinhardt13y00

My apologies, I was imprecise in my original comment. I was trying to get at the fact that "whether Turing machine M halts" is not actually a concrete question, as had been claimed above (I was assuming that the reason it was presumed to be concrete is because you can just watch the machine and it either halts or doesn't, and my point was that you can't actually just watch a machine to see if it will halt).

[-][anonymous]13y00

Whether a Turing Machine ever halts is a concrete question with a definite yes or no answer

This doesn't seem right. In different models, different TMs halt, and it's impossible to specify which model you really mean as settling the question. You can even decide, of your own free will, whether certain TMs halt or not (if you're simulated by them, say). So, it should rather be the more trivial "In any given structure, whether a TM execution defined on it halts, is a property of that structure."

[This comment is no longer endorsed by its author]Reply

[-]Shmi13y30

Please don't confuse math with "reality". Math as about axioms and proofs (well-formed finite strings), and is often a useful tool in mapping the territory, but it is just that, one of the tools.

If a question about reality turns out to be logically independent of a model M, then M is not a complete model of reality.

Quantum Mechanics is a classic counterexample, as far as we know, in a sense that there is no deeper underlying theory that would predict an outcome of a measurement when QM says it cannot be determined.

[-]Vladimir_Nesov13y40

Math as about axioms and proofs (well-formed finite strings), and is often a useful tool in mapping the territory, but it is just that, one of the tools.

Your formalist ideology is noted, but please don't state its (disputable) claims as clear truths.

[-]Shmi13y00

Your formalist ideology is noted, but please don't state its (disputable) claims as clear truths.

Not sure what you mean by "formalist", or " claims as clear truth", but feel free to provide a different definition of mathematics acceptable to a mathematician.

[-]Vladimir_Nesov13y30

Mathematics seemingly studies mathematical structures, guided by rather elusive criteria for what is worth studying, with axioms and proofs not obviously constituting the whole of its focus. In philosophy of mathematics, asserting that only formal statements and proofs make sense is known as formalism:

It has been claimed that “Formalists, such as David Hilbert, hold that mathematics is no more or less than mathematical language. It is simply a series of games...”

[-]dlthomas13y30

Quantum Mechanics is a classic counterexample, as far as we know, in a sense that there is no deeper underlying theory that would predict an outcome of a measurement when QM says it cannot be determined.

With MWI, this is incorrect - we do predict the outcome: all the branches.

[-]Shmi13y50

With MWI, this is incorrect - we do predict the outcome: all the branches.

The MWI gives an illusion of predictability ("Everything possible happens! We just don't see it because nearly all of it happens somewhere else to some other 'us'!"). Unfortunately, it can no more answer the question of which outcome an experiment will measure in "this world" than any other interpretation.

Even more unfortunately, and at a risk of a massive downvote, I hate to say it, but the MWI has become an official LW religion:

proclaimed to be true true by the founder: check
provides comfort to the masses: check
sets the group apart from others: check
impossible to falsify: check
makes one feel superior because of "deeper understanding of the world": check

[-]khafra13y50

How does MWI provide comfort to the masses? Michael Vassar is hardly the masses, but it makes him extremely uncomfortable--he called Quantum Immortality the most horrifying idea he'd ever had to take seriously, and I agree.

[-]Shmi13y50

I would think that most people would find the idea of living forever in some of the worlds at least somewhat comforting. It is even better than having an immortal soul: you get to live forever in the flesh, and you do not need to pay a tithe in any of the worlds.

That said, I was referring to something else, namely to the major discomfort of the essential unpredictability of any quantum experiment. In the MWI (or at least in some versions of it) the parallel worlds come into existence and sail apart as the decoherence takes hold and the off-diagonal contribution to the joint system/detector state decays away rapidly.

Everything seems predictable and some day maybe even computable. The only minor caveat is that you never get to observe these other worlds and bless your surviving copies with your dying breath (or receive the blessing of those gone before you).

[-]dlthomas13y30

Unfortunately, it can no more answer the question of which outcome an experiment will measure in "this world" than any other interpretation.

It doesn't fail to give an answer to the question - it makes the question incoherent.

"Which outcome an experiment will measure" is sitting before the experiment looking forward. With MWI, there is no world after the experiment looking backwards with a unique claim on being "this world." The answer to "will there be a me observing result X" will of course be yes. The question of which of those mes is the "real" one is misleading. What quantum theory does tell us, in MWI, is the total amount of surprise in the mes looking back.

[-]Shmi13y-40

...And we are back to square one, the unfalsifiability of an interpretation, which makes the adepts feel good about their "knowledge" without running any risk of it being shattered.

[-]Vladimir_Nesov13y80

If you suppose "interpretation" to be a distinction that can't be settled by observation, and simultaneously that any distinction must be settled by observation, then it's not clear what you're objecting to. These posts seem relevant: Belief in the Implied Invisible, You're Entitled to Arguments, But Not (That Particular) Proof.

[-]FAWS13y40

For your information: Not voting you down because you disagree with the MWI, but because you made a silly argument and then immediately replaced it with an entirely different argument with no acknowledgement that your original argument had been shown to be silly.

[-]dlthomas13y20

I wasn't feeling superior to you because you chose to reference non-MWI QM - I'm not confident about MWI myself, and would prefer we keep other interpretations alive until we can distinguish on the basis of evidence (or at least have a strong argument that space complexity deserves no place at all in our priors).

I am feeling superior to you now because you ignored a prevalent interpretation without giving mention to what interpretation you were using, and then when I tried to clarify you launched into a rant.

[-]prase13y00

Is it really necessary to publish one's superior feelings?

[-]dlthomas13y10

Generally? No, not at all. Here, it was specifically a response to statements to the effect of "you're only bringing up MWI as an excuse to feel superior."

[-]prase13y00

Still, I find it preferable if people keep their potentially offensive feelings private, even if these feelings arose as a reaction to being accused of having such feelings.

[-]dlthomas13y10

I offered the above more as explanation than defense. I certainly respect your point of view here; I have some further thoughts, but I'd rather sift through them a bit as I'm not sure they're actually coherent.

[-]prase13y00

Fair enough.

[-]Shmi13y-10

without giving mention to what interpretation you were using

The math of QM does not require an interpretation, so I refrain from using any.

[-]dlthomas13y20

Then refrain.

Quantum Mechanics is a classic counterexample, as far as we know, in a sense that there is no deeper underlying theory that would predict an outcome of a measurement when QM says it cannot be determined.

This is not refraining from picking a model - this is choosing to reify certain classes of interpretation. If you are saying, "The math is just what the math is, and says nothing more" then it doesn't purport to be complete in the first place, and isn't a counterexample.

[-]Shmi13y00

Seems like we are talking past each other (happens quite often whenever the MWI is mentioned), so I will disengage.

[-]FeepingCreature13y10

Quantum Mechanics is falsifiable; MWI vs Copenhagen is mathematically equivalent. I'd call it a preference rather than a religion.

[edit] Poster below states that they're not mathematically equivalent. I think a better way of saying it is "MWI is related to Copenhagen so that observable evidence for or against one is always and exactly observable evidence for or against the other as well. "

[-]Shmi13y20

I'd call it a preference rather than a religion.

Unfortunately, it is not treated as a preference. People use magic words like Occam's razor, Solomonoff induction and Kolmogorov complexity to justify why the MWI is better, without any attempt to quantify it. Well, I did make an attempt to quantify the complexity in one of my comments. Predictably, at least in the hindsight, there was little interest in discussing the validity or the consequences of this approach.

[-]ksvanhorn13y10

At least one well-known physicist not only believes that the MWI can be falsified... he suggests that it has been falsified:

http://www.analogsf.com/0409/altview2.shtml

[-]Shmi13y00

I suspect that he misinterprets, as it were, what an interpretation is, namely, a way of thinking that elucidates the underlying mathematical framework. He seems to think that different interpretations can make different predictions based on the same math:

We are led by the Copenhagen Interpretation to expect that the positions of the interference minima should have no particular significance, and that the wires should intercept 6% of the light they do for uniform illumination.

...

Thus, it appears that both the Copenhagen Interpretation and the Many-Worlds Interpretation have been falsified by experiment.

Does this mean that the theory of quantum mechanics has also been falsified? No indeed! The quantum formalism has no problem in predicting the Afshar result. A simple quantum mechanical calculation using the standard formalism shows that the wires should intercept only a very small fraction of the light. The problem encountered by the Copenhagen and Many-Worlds Interpretations is that the Afshar Experiment has identified a situation in which these popular interpretations of quantum mechanics are inconsistent with the quantum formalism itself.

I would say that, more likely than not, his mental model of what an interpretation is is different from what physicists tend to mean. It does not help that he has an ax to grind, as the author of his pet "transactional" interpretation.

[-]ksvanhorn13y00

Reread this statement, which you quoted: "The problem encountered by the Copenhagen and Many-Worlds Interpretations is that the Afshar Experiment has identified a situation in which these popular interpretations of quantum mechanics are inconsistent with the quantum formalism itself."

The implication is that Copenhagen and Many-Worlds are not valid interpretations, since (he claims) they are inconsistent with the formalism. (I'm not sufficiently well-versed in QM to evaluate this claim, unfortunately.)

[-]pragmatist13y00

Copenhagen and Many Worlds do not employ the same math. Many Worlds posits a single dynamical evolution law, given by Schrodinger's equation. Copenhagen supplements this with an intermittent stochastic collapse process (Von Neumann's Process 2). So Copenhagen vs. MWI is a question open to empirical test.

There are certain interpretations that are empirically indistinguishable from MWI. Bohmian mechanics is an example, although even here the math is different but this difference is postulated to be epistemically inaccessible.

EDIT: I think calling Copenhagen, MWI, Bohm, GRW, etc. different interpretations of a single theory is pretty misleading, suggesting that they are different models of the same axiomatic system. They should really be regarded as different theories, with a large amount of overlap in their mathematical structure.

[-]Shmi13y10

There is no "intermittent stochastic collapse process" anywhere in the math of QM. The measurement is a black box with the Born rule to decide the outcome. Bohm is a different story, and not a happy one.

[-]pragmatist13y00

The measurement process in the orthodox interpretation isn't just a means for determining outcomes. It also has an effect on the subsequent evolution of the wave function. There is a discontinuity in the dynamics before and after a measurement. I don't see how that wouldn't count as part of the math of the theory.

[-]Shmi13y00

True, but there is nothing stochastic about this. Measurement is an external event controlled by an observer. The Born rule and the jump into an eigenstate is the math of it, nothing more, nothing less. The "Von Neumann's Process 2" is an unnecessary interpretational mumbo-jumbo.

[-][anonymous]13y10

Surely QM can't be a classic counterexample of anything.

[-]Shmi13y10

classic != classical. English is weird...

[-]dlthomas13y00

Valid, but I've a high confidence grandparent was just a joke anyway, and classic ~ classical enough for that...

[-]komponisto13y20

GP

Please do not invent new abbreviations without formally introducing them first.

(Yes, I can figure out what it means, but I shouldn't have to. One should be able to use simple recognition to understand an abbreviation, without having to make any inference.)

[-]AlephNeil13y20

Suppose we had a model M that we thought described cannons and cannon balls. M consists of a set of mathematical assertions about cannons

In logic, the technical terms 'theory' and 'model' have rather precise meanings. If M is a collection of mathematical assertions then it's a theory rather than a model.

formally independent of the mathematical system A in the sense that the addition of some axiom A0 implies Q, while the addition of its negation, ~A0, implies ~Q.

Here you need to specify that adding A0 or ~A0 doesn't make the theory inconsistent, which is equivalent to just saying: "Neither Q nor ~Q can be deduced from A."

Note: if by M you had actually meant a model, in the sense of model theory, then for every well-formed sentence s, either M satisfies s or M satisfies ~s. But then models are abstract mathematical objects (like 'the integers'), and there's usually no way to know which sentences a model satisfies.

[-]ScottMessick13y20

Scott Aaronson (a well-known complexity theorist) has written a survey article about exactly this question.

[-]Manfred13y10

Is there anything that suggests that this is the case for P vs. NP?

[-]DanielLC13y00

If ZFC and P vs NP are independent, this means that it's impossible to give a proof that P=NP with ZFC. Since an example of a polynomial-time algorithm that can solve an NP problem would be such a proof, any such algorithm must be impossible to state in ZFC. Any algorithm we can actually run can be stated in ZFC. As such, this would mean that P!=NP. You'd just have to prove it in ZFC+1, which is ZFC with the additional axiom that ZFC (the original, not ZFC+1) is consistent.

[-]paulfchristiano13y120

[-]dlthomas13y10

Elaborate, please.

[-]paulfchristiano13y110

I'll write down an algorithm that solves SAT in time N^k if any algorithm does.

On SAT instances of size T, enumerate all algorithms of size up to log(T); for each one, consider all SAT instances of size up to log(T); run each algorithm for time log(T)^k, outputing 0 if they don't halt, and compare its output to the result of a brute force search.

Take the shortest algorithm which worked in each of these tests, and use it to answer your original SAT query of size T (aborting and outputing 0 if it takes more than T^k time).

This entire process takes time poly(T). Moreover, suppose there is an N^k time algorithm which solves SAT correctly and let A be the shortest such algorithm. Then there is a finite constant T0 such that all shorter algorithms than A fail on some SAT instance of size at most T0. Then the algorithm I described works correctly for all SAT instances of size at least 2^(T0 + |A|).

(Edit: this argument is silly; you can just run all programs of size log(T) and output a solution if any of them find one)

Edit: Note in particular that the algorithm which takes k = BB(10^10) and does a brute force search instead for T < BB(10^10) is guaranteed to solve SAT in poly time, provided that any algorithm does. Realistically, I think taking k = 10 and doing a brute for search for T < 10^10^10 is virtually guaranteed to solve SAT in poly time, if any algorithm does (and I can actually write down this latter algorithm).

[-]AlephNeil13y20

Perhaps a slightly simpler way would be to 'run all algorithms simultaneously' such that each one is slowed down by a constant factor. (E.g. at time t = (2x + 1) * 2^n, we do step x of algorithm n.) When algorithms terminate, we check (still within the same "process" and hence slowed down by a factor of 2^n) whether a solution to the problem has been generated. If so, we return it and halt.

ETA: Ah, but the business of 'switching processes' is going to need more than constant time. So I guess it's not immediately clear that this works.

[-]dlthomas13y00

Very interesting.

[-]orthonormal13y00

Exactly. For a more familiar example, the independence of the continuum hypothesis from ZFC means that we'll never stumble across a set of intermediate cardinality while doing an analysis problem (otherwise, we'd have a disproof), and so the CH is valid in a practical sense even though formally undecidable.

Generally speaking, if a statement is undecidable and claims the existence of something which could be effectively verified if it were found, then for practical purposes you can assume it's false.

EDIT: Oops- see paulfchristiano's comment on why P vs. NP isn't a case of this principle. I think the general principle is still OK, I just forgot about the whole "ability to effectively verify" bit in this case.

[-]cousin_it13y60

See paulfchristiano's comments. The mistake in DanielLC's comment is that, even though any polynomial algorithm can be "stated in ZFC", the proof that it runs in polynomial time doesn't necessarily lie within ZFC, or ZFC+Con(ZFC), or any other system you can name in advance.

[-]orthonormal13y00

Ah, thanks.

[-]Douglas_Knight13y00

It is not clear that our universe has infinite computing power. If it is finite, then there is a finite complete description of it. Maybe that finite description even fits in the universe. But we can't, in the universe, compute all the consequences of the description. If the universe is infinite and able to simulate infinite Turing machines, such as Conway's game of Life, then Gödel's theorem applies, as others explain. There are also intermediate possibilities, such as the universe is infinite, but we are not able to exploit it for computation, but a positivist might classify that as finite. I think that the state of the art is that this is the case, due to the cosmological constant.

Moderation Log

63Comments