Author |
Topic: NONCONSTRUCTIVE P=NP (Read 8979 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
NONCONSTRUCTIVE P=NP
« on: Sep 9th, 2002, 3:05pm » |
 Quote  Modify
|
You've made the breakthrough every theorist dreams of: you've solved P vs NP. Surprisingly enough, you've shown that P=NP, but sadly your proof was non-constructive. Design a poly-time program to solve SAT.
So I think the idea is this, after consulting some colleagues:
You can list all the programs in the universe, and timeshare amongst them such that each program gets some arbitrary constant fraction of cpu cycles. For instance, the 1st program might get 1/2 the time, the 2nd might get 1/4 of the time, the 3rd 1/8 of the time, etc..
Then you run all these programs, alternating between them. Whenever a program claims to have an answer for SAT, you can quickly check the validity of the answer by simply evaluating the SAT expression with the program's proof.
Since P=NP, we know that one of these programs will be the poly-time program that can solve SAT. Even if this needle in the haystack is the 10,000th program in our list, it will solve SAT in poly-time, modulated by some constant factor (in my example, a factor 1/(2^10000)).
I'm not comfortable with the part about listing all possible programs though. Aren't there an infinite number, which I could not store on a finite computer hard disk?
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
AlexH
Full Member
Posts: 156
|
 |
Re: NONCONSTRUCTIVE P=NP
« Reply #1 on: Sep 9th, 2002, 6:55pm » |
Quote Modify
|
You've got it William. Its true there are an infinite number of programs, but you'll only look at a polynomial number of them, in fact with the timeslicing method you describe, you'd actually wind up only looking at a logarithmic number of programs.
Let S be the first program (under some ordering of programs) that solves SAT in polytime, call its position in the ordering c. c is just a constant (albeit a big one). If f(n) is the running time bound of S on inputs of length n, then you're only going to look at O(c+log f(n)) programs before you've given S the O(2log f(n) = f(n)) time it needs to finish. Overall running time is O(2cf(n) log f(n)), but c is constant so this is O(f(n) log f(n)). I'm sweeping things like cost of timeslicing and the time to check answers under the rug here, but those are obviously polynomial so it doesn't change the essential point that our running time is polynomial in n (with amazingly ridiculous constants).
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #2 on: Nov 18th, 2002, 1:01pm » |
Quote Modify
|
So suppose I discover a nonconstructive proof that P=NP. In light of the fact that the polynomial running time may be scaled by ridiculously large constants, would the men in black suits still come to kill me?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #4 on: Jan 8th, 2003, 2:07pm » |
Quote Modify
|
The sad thing is you'd never be sure that the first program to solve it was a poly-time SAT program...
Even worse, you'd have to check all the programs before you started to make sure they didn't halt your machine 
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #5 on: Sep 16th, 2003, 11:58pm » |
Quote Modify
|
In retrospect, after discussing this problem with some colleagues, I'm not convinced by the solution anymore. If AlexH doesn't show up again, I'll have to e-mail him to get over here 
First to answer James's concern: We don't need to restrict a priori the class of programs we're running to only poly-time programs; nor must we devise some way to check a posteriori if a program which solves our instance of SAT solved it in poly-time. We are arguing that the universal emulator which runs all these other programs will solve SAT in poly-time, and hence the emulator is the constructive proof that P=NP.
Let's describe the previously mentioned logarithmic timeslicing scheme in more detail. Consider the following interesting sequence:
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 5 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
The sequence is generated by the following rule: the natural number n appears every 2n elements in the sequence. So 1 appears as every other element in the sequence, 2 appears as every fourth element, etc.
Interpret this sequence as a follows: if the ith number in the sequence is k, then the ith clock cycle is allocated to running program k. (Program k is the kth program in the denumerable set of all programs.)
Since P=NP, there exists a natural number m such that program m solves SAT. Let x be the size of the input problem. Thus if program m takes p(x) time to solve SAT, where p(x) is a polynomial in terms of x, then our emulator will solve SAT in time
2mp(x)t(x)
where t(x) = a polynomial amount of time in terms of x, required to verify p(x)'s solution. Since SAT[in]NP, verification should only take polytime. Note that m is some fixed integer. Thus our emulator still solves SAT in polytime, despite the fact that the constant 2m could be "amazingly ridiculous."
...
So all this would have been fine, but here's my problem: how do you polytime verify whether a program is lying to you when it says that an instance of SAT is unsatisfiable? For satisfying instances, there exists a simple polytime certificate -- you just evaluate the truth assignment which causes the formula to be true. But is there a polytime certificate for showing there is no truth assignment, given that P=NP?
More thoughts: The class co-NP consists of problems that are the complement of problems in NP. (So determining whether a SAT formula has no satisfying assignment would fall in co-NP.) Since P = co-P, it follows that P=NP[to]NP=co-NP. Can we use this to somehow construct polytime certificates for problems in co-NP?
Sidenote: With regards to James's seemingly frivolous comment about the emulator being halted by a program it's emulating ... I'm not sure what to say about this. At first I thought it was clearly impossible, but now I'm not sure how to rigorously argue that this is not an issue. I guess your concern is that the program you're running could cause the emulator to unintentionally halt, hacking the emulator like a trojan? So the question is whether an emulator can emulate a program that is designed to halt an emulator which emulates that program? Does this get into issues of Turing-uncomputability / Godel's Incompleteness Theorem?
Note: Thanks to the gracious John Leen for clarifying some issues to me. He also tipped me off to the following fascinating fact I didn't know before: the first (2[supn]-1) numbers in the 1 2 1 3 1 2 ... sequence happens to be the solution for the Towers of Hanoi problem with n discs! I guess I never studied the Hanoi problem very deeply.
|
| « Last Edit: Oct 4th, 2003, 1:42pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Rezyk
Junior Member
Gender:
Posts: 85
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #6 on: Nov 8th, 2003, 4:34pm » |
Quote Modify
|
on Sep 16th, 2003, 11:58pm, william wu wrote:So all this would have been fine, but here's my problem: how do you polytime verify whether a program is lying to you when it says that an instance of SAT is unsatisfiable? For satisfying instances, there exists a simple polytime certificate -- you just evaluate the truth assignment which causes the formula to be true. But is there a polytime certificate for showing there is no truth assignment, given that P=NP?
More thoughts: The class co-NP consists of problems that are the complement of problems in NP. (So determining whether a SAT formula has no satisfying assignment would fall in co-NP.) Since P = co-P, it follows that P=NP[to]NP=co-NP. Can we use this to somehow construct polytime certificates for problems in co-NP? |
|
Yeah, since SAT would be in co-NP, there would have to exist polytime certificates...you'd even be constructing them with your iteration-over-all-programs already.
The problem is that there's no obvious way to recognize or use them in the right way. If you could explicitly find any polytime verifier for NO-instance witnesses of SAT, you'd have solved NP ?= co-NP.
I don't think it helps to just know that there is polytime certificates being generated anyways...since actually any output could be considered a certificate by this polytime verifier:
1. Take the certificate and throw it away.
2. Run the polytime algorithm to solve SAT yourself.
3. Return the correct answer.
Note that you can use the reasonings so far to develop an answer for polytime solving integer factorization (and probably all other problems in NP [smiley=bigcap.gif] co-NP), because we know polytime-verifiers for both YES and NO witnesses of it.
|
|
IP Logged |
|
|
|
Heya Gosper
Guest
|
admittedly I don't understand maths as well as l like... but doesn't your supposed proof have the fatal flaw of circular logic? You keep saying: "Since P=NP, there exists blah blah blah"
Hey, that's what you were trying to prove. You can't use it as an axiom to bootstrap your proof.
I think you mean that IF P=NP then your monstrous emulator would be able to prove it... but that is not a proof at all unless you provide a case where P!=NP would create a contradiction.
Maybe I'm missing the point here. Isn't the whole point that we don't know whether a poly-time algorithm for SAT exists at all? Might the emulator not run an infinite number of programs and still not solve the problem... in infinite time (decidedly worse than polynomial).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #8 on: May 18th, 2004, 4:37am » |
Quote Modify
|
The problem start off with
Quote:| You've made the breakthrough every theorist dreams of: you've solved P vs NP. Surprisingly enough, you've shown that P=NP, but sadly your proof was non-constructive. Design a poly-time program to solve SAT |
|
So that P=NP is a given for this problem. It's not something to proof, but something to use in the construction of your SAT-program.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Heya Gosper
Guest
|
Oh dear
Sorry, I didn't read the question properly...
Actually I came upon the forum FIRST and was incensed enough to reply... then I went back and looked at the rest of the site. I guess that's an oversite.
I am currently trying to prove P = NP or vice-versa so the postings kind of confused me and got my hopes up.
KUTGW, Heya
|
|
IP Logged |
|
|
|
Heya Gosper
Guest
|
I have a prisoner's dilemma for ya...
Say this computer scientist and gangsta Hazy H has an idea for solving P=NP. The problem is, MC H knows that he does not have the math skills to prove his idea. H wants more information to work out whether the idea has merit, for he feels that a fresh, lateral perspective is what is required to solve the problem, and not necessarily a genius for math.
How can the suspicious rapper find out (from smarter geeks than he) whether the idea will work without forgoing the million dollar prize?
Of course, without their help H may never solve the stupid problem at all, and will win nothing.
For extra credit, is Hazy's problem in P, NP, or both? (proof please).
|
|
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #11 on: May 20th, 2004, 10:17am » |
Quote Modify
|
The usually accepted answer to the prisoner's dilemma (at least, the best I've found) is to ask yourself "do you want the other person to win or lose?" However, this instance isn't a pure example of the prisoner's dilemma, since it lacks the second person making a choice (unless, of course, you assume that the said geeks could choose to share credit rather than take the glory for themselves). So, in this instance, I would imagine the best approach would be ask them and find out if they're happy to share credit - after all, you're not losing anything by trying, since the options you've suggested so far are lose-lose...
|
|
IP Logged |
|
|
|
benetin
Newbie
Posts: 1
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #12 on: Mar 28th, 2006, 7:57pm » |
Quote Modify
|
Here is the problem in the solution sketched by Bill: If the input is not satisfiable, the algorithm will never be able to say "no".
May I ask what is the origin of this problem? It will be nice if I am confirmed there is a solution to it. I already spent 30 minutes on it and all I got is the similar ideas as Bill outlined.
BTW, thanks for this excellent web. Now I have a place to kill a lot of time.
|
|
IP Logged |
|
|
|
River Phoenix
Junior Member
Gender:
Posts: 125
|
|
Re: NONCONSTRUCTIVE P=NP
« Reply #13 on: May 21st, 2009, 5:55pm » |
Quote Modify
|
benetin is right, this is a classic algorithm, attributed to Levin, but it only finds satisfying assignments in polynomial time given that they exist.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove