Re: basic query regarding NP Complete...

From: Markus Triska <triska@xxxxxx>
Date: Sat, 26 Aug 2006 13:49:07 +0200

"Prakash" <helloprak@xxxxxxxxx> writes:

Question in short... Why does it always have to start with SAT ?

It doesn't have to - however, it's relatively simple to encode a
non-deterministic Turing machine as an instance of SAT polynomial in
the input such that the resulting formula is satisfiable iff the
Turing machine accepts its input.
.

References:
- basic query regarding NP Complete...
  - From: Prakash
- Re: basic query regarding NP Complete...
  - From: Kai Schories
- Re: basic query regarding NP Complete...
  - From: Prakash
- Re: basic query regarding NP Complete...
  - From: Russell Easterly
- Re: basic query regarding NP Complete...
  - From: Prakash

Prev by Date: Re: Shortest path with intermediate nodes algorithm
Next by Date: Re: basic query regarding NP Complete...
Previous by thread: Re: basic query regarding NP Complete...
Next by thread: Re: basic query regarding NP Complete...
Index(es):
- Date
- Thread

Relevant Pages

Re: *Quantum Computing* expert Bill Munro
... time on a non-deterministic turing machine, but which, in worst case, ... If P == NP, then there exists some algorithm, which, on a deterministic ... solves one of those problems in polynomial time. ...
(sci.crypt)
Re: *Quantum Computing* expert Bill Munro
... Benjamin Goldberg wrote: ... or is there no such connection? ... > time on a non-deterministic turing machine, but which, in worst case, ... accepted) in p-time on a non-deterministic Turing machine. ...
(sci.crypt)
Re: [Full-Disclosure] Coming soon: CPU fix for buffer overflows
... On Tuesday 24 February 2004 15:02, Marek Isalski wrote: ... > A non-deterministic Turing Machine is a bit like having an infinite ...
(Full-Disclosure)
Re: [Full-Disclosure] Coming soon: CPU fix for buffer overflows
... On Tuesday 24 February 2004 15:02, Marek Isalski wrote: ... > A non-deterministic Turing Machine is a bit like having an infinite ...
(Full-Disclosure)