New answers tagged np
1
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.
0
Your algorithm builds a tree, not a single path.
0
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 ...
2
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 ...
3
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.
1
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
