[Solved]: Can Circuit Value Problem or HORN-SAT be reduced to PATH problem?

Problem Detail: 

PATH = {(X,R,S,T) | exists an x in S that is admissible} Where R is a relation of X x X x X, S is a unary relation of X and T is a unary relation of X aswell. An x element of X is admissible if it is in T or if there is two elements y z both admissibles, where (x,y,z) is in R.

So, is there any logspace reduction from CVP or HORN-SAT to this problem, so I can prove that PATH is P-Complete?

Asked By : gnar

Answered By : Yuval Filmus

Hint: Reduce from the monotone circuit value problem. Let $X$ be the set of all inputs and internal gates in the circuit. Choose $T$ and $R$ so that an element is admissible if the corresponding input or gate is true (each AND gate will require one triple in $R$, each OR gate will require two). Choose $S$ to be the indicator of the output gate to complete the proof.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42901

3.2K people like this

 Download Related Notes/Documents