New answers tagged


3).. . Also at each step I disregard the roads that has been travelled already for that particular path. In order to do that, you must be running Dijkstra on a graph with exponentially more vertices than the input graph.


Problem A is in NP if: B is in NP and you can reduce B to A in polynomial time -> B $\leq_p$ A Not quite right. The class $P$ is a subset of $NP$ anyway, and hence A is already $NP$ if it is in $P$. The question is whether A is in P or not. By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of ...


Under the assumption that $NP\neq \mathrm{co}NP$, we have that: $$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$ Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$. Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due ...


As Yuval Filmus already mentioned in the comments, because of the time hierarchy theorem, we know $\mathsf{P} \neq \mathsf{EXP}$. Hence, any $\mathsf{EXP}$-complete problem is an example. These include, for instance, generalized chess and checkers.


This isn't really a natural example, but a natural technique (which I'm leaving as an answer instead of a comment since I think it's still valuable, and it's clearly too long): we can use a diagonal argument. Specifically, while we can't tell whether a Turing machine runs in polynomial time, we can whip up a list of polynomial-time Turing machines such that ...

Top 50 recent answers are included