New answers tagged

0

You can reduce from $3$-coloring. Given an instance (graph) $G=(V,E)$ of $3$-coloring, create a tri-graph $G'=(V', E')$ by transforming each edge $e=(u,v) \in E$ to a tri-edge $(u,v,z_e)$ in $G'$ (where $z_e$ is a new vertex). A 3-coloring $c : V' \to \{1,2,3\}$ of $G'$ induces a $3$-coloring of $G$: simply color $v \in V$ with color $c(v)$. A 3-coloring $c :...


2

Hint: does being in P have something to do with the length of the input?


1

This might help you: The AKS primality test is in P.


1

The answer to your question is formally "yes". This is because one possible Turing machine that halts iff P=NP is either (i) a Turning machine that always halts or (ii) a Turing machine that never halts (regardless of its input). However, the following argument might be closer in spirit to what you are asking: Assume that $P=NP$ is not independent ...


Top 50 recent answers are included