Re: P-Time Circuit SAT

klaus hoffmann <nospam@xxxxxxxxxxxx> wrote:

> The "usual suspect" is the recursive funcion which examines subcircuits
> for tautology in linear or quadratic time. This part contains too much
> handwaving to be verified or falsified.

Yes. His test for contradiction (all 0's) or tautology (all 1's) is a
test for Satisfiability, and if he can test a circuit yes/so for SAT,
he can find a satisfying assignment by probing for
SAT while twiddling input bits.

So the only thing we have to check is his magic recursive function which
allegedly determines contradiction or tautology of the circuit and all
subcircuits.

He only checks two cases, and determines that an AND can output a 1 by
recursively checking both inputs for 1, and determines an OR can output
a 0 by recursively checking both inputs for zero. Conspicuously absent
are the cases where the AND is 0 and the OR is 1, which can represent
more complex situations than both gate inputs being constants.

If he had just written a little program to check his algorithm, he would
of course have noticed this. His tabular heuristic for finding a
satisfying assignment after the magic recursive function does its thing
is equivalent to unit clause propagation.

Still, I find reading and analyzing the neverending stream of NP=/!=P
proofs an entertaining exercise. Someone has actually made a web page
giving a template for a typical such argument in this newsgroup.

http://geomblog.blogspot.com/2004/04/meta-proof.html

--
Enrico Dirac
Amplified Panatropic Computations Network Analyst
"I tolerate this century, but I don't enjoy it."
.

Quantcast