Re: P-Time Circuit SAT
- From: klaus hoffmann <nospam@xxxxxxxxxxxx>
- Date: Tue, 10 Jan 2006 22:19:49 +0100
Enrico Dirac wrote:
Have we discussed why this is wrong? I didn't see any references to it in Google Groups, and it's a recent paper.The "usual suspect" is the recursive funcion which examines subcircuits for tautology in linear or quadratic time. This part contains too much hanwaving to be verified or falsified.
http://arxiv.org/pdf/cs.CC/0511071
A polynomial-time algorithm for Circuit-SAT
Francesco Capasso
capassofrancesco@xxxxxxxx
Abstract. In this paper is presented an algorithm that, in polynomial time and space in the input dimension, determines if a circuit describes a tautology or a contradiction. If the circuit is neither a tautology nor a contradiction, then the algorithm finds an assignment to the circuit inputs such that the circuit is satisfied.
The author should write a SAT-solver (reasonably easy) based on it and try it with hard SAT-Problems
hth
Klaus
.
- Follow-Ups:
- Re: P-Time Circuit SAT
- From: Enrico Dirac
- Re: P-Time Circuit SAT
- References:
- P-Time Circuit SAT
- From: Enrico Dirac
- P-Time Circuit SAT
- Prev by Date: Minimal transducer that maps one word into another
- Next by Date: Re: Need help with terminology
- Previous by thread: P-Time Circuit SAT
- Next by thread: Re: P-Time Circuit SAT
- Index(es):
Relevant Pages
|
