I like Scott Aaronsons approach: Using NP hardness asumption as a physical constraint and seeing what follows. https://arxiv.org/abs/quant-ph/0502072
Direct PDF link for the lazy (e.g. me):
The P=?NP Poll (2002) [pdf]
21–30 of 87 posts
Re: The P=?NP Poll (2002) [pdf]
#22Earlier quoted context omitted.
It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
It might be useless for solving NP problems, but that's not the "point" of P=NP per say. P=NP is an intrinsically interesting math problem.
And the parent is pointing out that if P=NP, we already have a construction.
So (if his opinion was presented accurately), Knuth is wrong about a positive proof being non-constructive.
---
I believe there are already known problems whose best solution is O(n^k) for arbitrarily high k. So yeah, naturally not everything will be practically tractable.
Re: The P=?NP Poll (2002) [pdf]
#23Earlier quoted context omitted.
It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
If the minimum exponent of a problem as natural as 3-SAT ended up being ~1000, that might be even more fascinating than the fact that it's polynomial.
Re: The P=?NP Poll (2002) [pdf]
#24Earlier quoted context omitted.
It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
This argument is useless since polynomial time is just as intractable as exponential time if the exponent is large. For example, lets say that we found a way to solve all np problems in n^1000 time, would that change anything? No, there aren't even 2^1000 atoms in the universe so we will only be able to solve it for the case n=1.
Your argument supports the view that P is a useless concept, not that that argument is pointless.
Re: The P=?NP Poll (2002) [pdf]
#25A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…
> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)
> If P = NP, then P^X = NP^X for any oracle X, right?
Edit: No, I think. See child comment by JadeNB.
Probably wrong { Yes, since we could just not invoke the oracle. But people do this sort of stuff to study it backwards e.g. what do P^X and NP^X (and any class^X) tell us about P and NP (and any other class). }
I hope this is clearer, let {A, B, C, ...} be the set of all oracles.
For TM + A:
P^A is the class of problems that can be done in P time on this machine.
NP^A is the class of problems that can be done in NP time on this machine.
Similarly for
TM + B
TM + C ...
This theorem says that if we choose one of these oracle machines uniformly at random then P =/= NP in _its_ model of computation a.s.
This is an entirely probabilistic statement about machines that are more "powerful" than standard TMs.
Re: The P=?NP Poll (2002) [pdf]
#26Knuth's perspective on this topic is quite interesting, bordering on the infuriatingly frustrating: he seems to be of the opinion that p=np, but any proof we find for that will be non-constructive and the actual algorithm will evade us. http://www.informit.com/articles/article.aspx?p=2213858
It's worth noting that if P=NP, then there's already a known (though highly impractical) algorithm which can solve any given NP problem in polynomial time: https://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial...
Fascinating. In fact by devoting half of its time to the first algorithm, a quarter to the second, and so on, it will solve it in the same big-O as the most efficient algorithm! (Albeit with a horrible constant.)
That said, this algorithm does not solve the decision problem because it can never return a no. Only a yes if there is one to be found.
Re: The P=?NP Poll (2002) [pdf]
#27A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…
Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?
Re: The P=?NP Poll (2002) [pdf]
#28A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…
Anyone got suggestions for what a web dev should read or what classes he should take to understand what this guy is saying?
Theory of Computation
Re: The P=?NP Poll (2002) [pdf]
#29A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. An oracle is a black box that can solve a particular decision problem in O(1). The notation means e.g. P^SAT = class of all problems that can be solved in P time with a machine that has an oracle for SAT. It gets really ingesti…
> A really cool result which seems relatively unknown is that if we augment our Turing machines with an oracle X chosen uniformly at random from all oracles then P^X =/= NP^X with probability 1. Wait, this has to be conditional on something. If P = NP, then P^X = NP^X for any oracle X, right? (It's been a while since my theoretical CS class, so maybe it's my naïve assumption that's not true.)
It's tricky and the notation confuses things a bit.
P and NP are not the machine, but the set of problems solvable by deterministic/non-deterministic Turing machines limited to a polynomial number of steps. P^X is set of problems solvable by a deterministic Turing machine with access to oracle X, which is fairly straight forward, but need have little to with P. Similarly, NP^X is the set of problems solvable by a non-deterministic Turing machine with access to oracle X. However, this means if there's any input it could ask X to get an answer it can use to solve the problem, it can solve the problem, which may be vastly more efficient than trying to construct the right question to ask.
Essentially it boils down to: Just because two different models of computation can solve the same problems, does not mean that when augmented by the same oracle can solve the same problems (they can access the oracles in different ways).
Re: The P=?NP Poll (2002) [pdf]
#30Maybe the solution to P=NP problem is P=NP.