# Questions tagged [p-vs-np]

The tag has no usage guidance.

283 questions
Filter by
Sorted by
Tagged with
127 views

### Will this proof method work for p vs np

Given, that NP is the class of all problems that a non-deterministic Turing machine can solve in polynomial time, and proving P = NP will prove that there is no difference between a non-deterministic ...
44 views

### Can we use XOR's forced branching to show that NP!=P

Backstory: As happens, every now and then, one encounters an idea, prompting the question: Could I use this to prove that NP==P, or vice versa NP!=P So then, today I got to trying to show that NP!=P ...
• 15
1 vote
35 views

• 367
49 views

### Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$?

Is there an oracle $A$ with $P^A = NP^A$, but $EXP^A \not= NEXP^A$ ? I found a proof with padding arguments (wikipedia), that $$P = NP \Rightarrow EXP = NEXP$$ If an oracle $A$ exists with $P=NP$ ...
1 vote
177 views

### What could $P = NP$ imply about arbitrary Turing machines?

My question: What $P \not= NP$ or $P = NP$ could imply about arbitrary Turing machines and arbitrary computations? I assume that a partial and incomplete, but objective answer to this question exists ...
43 views

### Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?

I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$. What is known is that the ...
1 vote
199 views

1 vote