10 questions linked to/from How not to solve P=NP?
93 views

### NP != P Proof Requirments [duplicate]

I have been examining the NP = P problem and I am wondering, why is proving or disproving NP = P hard? For example, why wouldn't a proof such as the following be adequate? Suppose a million doors were ...
243 views

### what are the basic/typical/common mistakes in P=NP claims? [duplicate]

the P vs NP problem attracts a lot of attention, not all of it desirable, for a wide variety of reasons. there are many P=NP claims eg on this widely cited list maintained by mathematician Woegeorgi, ...
88 views

### Are there theoretical reasons for believing that P=NP is harder than other complexity problems? [duplicate]

I have a meta-complexity question: Are there reasons to believe that it is more difficult to prove P != NP than, say PSPACE != EXPTIME or BPP != BQP?
141k views

### What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
24k views

### If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

Many seem to believe that $P\ne NP$, but many also believe it to be very unlikely that this will ever be proven. Is there not some inconsistency to this? If you hold that such a proof is unlikely, ...
772 views

### How can Computer Science theories and inquiries be resolved?

It's probably possible to prove that P ≠ NP, that one-way functions exist, and that parity games cannot be solved in polynomial time (yes, I've been reading through this list), but how would we go ...
2k views

### Why are non-relativizing proofs preferred to relativizing ones?

I apologize, but even after these two other posts: here and here I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle: Why ...
1k views

### If I solve hard instance, therefore I prove NP=P? [duplicate]

If someone (off-topic) asks a question (on-topic) like this: Suppose that he claims that $\mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that ...
2k views

### How to prove polynomial time equivalence?

Define the problem $W$: Input: A multi-set of numbers $S$, and a number $t$. Question: What is the smallest subset $s \subseteq S$ so that $\sum_{k \in s} k = t$, if there is one? (If not, ...
728 views

### What makes it so difficult to prove P =/≠ NP? — The subset sum issue [closed]

I can't understand or imagine some fact about NP-hard problems. If I understand it correctly there is only one polynomial-time algorithm needed – for whichever NP-complete problem – to ...