Non-determinism (was Re: NP and co-NP)
Dr A. N. Walker
Alex Lopez-Ortiz wrote:
> Indded, you must define the termination condition. In this case it
> is one of the forking computations reaching a goal, there is no
> communication at all within processes.
And yet the "arbiter" knows when the goal is reached, and
each process must know which part of the computational tree it is
following [else two clones must do identical computations]. Let's
carry on ...
> Nope. Think about it as if there was an arbiter at the end of all
> computation paths. You don't have to communicate to your siblings the fact
> that you have found a satisfying tour, the arbiter declares you the
> "winner" so to speak.
Fine. But in this case, if there is no satisfying tour, then
within [known and bounded, for HC] polynomial time the arbiter knows
there is no winner and hence that this is a "no" instance. And you
are saying rather more than "You don't have to communicate ..."; you
*must* not communicate. If the arbiter knows the answer, why can't
we? And *how* does the arbiter know? You can certainly define
formalisms in which this works, but it is taking us further and further
away from familiar ground.
This is computing, but not as we know it, Jim.
> This is akin to ho #P, Maj-P and Parity-P are defined.
Um, well, yes and no. Clearly the arbiter could collect
all the results and do the counts. But equally, each parent could
collect the results of its children, so that only the root process
needs to communicate externally. From a practical point of view,
this seems [to me] more natural -- it's akin to how we do lots of
recursive things with data structures.
> My experience is that students have a hard time grasping the formal
> idea behind guessing. While I think most would have no problem understanding
> your Nothingam pub-crawl analogy (I like ti by the way), when it comes to
> formally defining nondeterminism it just sounds to hocus-pocus to most.
It *is* hocus-pocus! Students, except the very brightest,
have a hard time grasping *any* formal idea. Luckily, for the most
part, only those who go on to do research in the area really need
the formalisms.
We have a similar problem [eg] in u-g maths, with topics
like "continuity". Everyone understands the informal "continuous
<=> can be drawn with one stroke of the pen"; only a few really
understand the "proper" epsilon-delta definition [though enough can
parrot it to get through exams]; the challenge to the teacher is
to find an intermediate explanation that the students understand
but that is easier to apply to real problems; and the second
challenge to the teacher is to explain why students have to use
the epsilon-delta definition when teachers never use it themselves
in their own work.
I believe that every mathematician [and a majority of CS
professionals] *ought* to have a good working idea of what a Turing
machine is, likewise computable number, member of P, of NP, what
NP-complete means [and signifies], etc [and of course many other
topics in other areas of maths/CS]. We can either tackle these
concepts in terms of computers, programs, discs, processes, etc
with which our students are [at least hazily] familiar, and accept
that the concepts will be slightly fuzzily explained and that those
who go on to research will need to learn more precise definitions
later; or start with some formalisms, in which a Turing machine
is a bit like a computer but not so alike that you are allowed to
use the similarities, and rapidly lose most of the students, but at
least the research students start fully armed.
In my teaching roles, I know which I prefer.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
Alex Lopez-Ortiz
In article <34FC43...@maths.nott.ac.uk>,
Dr A. N. Walker <a...@maths.nott.ac.uk> wrote:
>Alex Lopez-Ortiz wrote:
>> Indded, you must define the termination condition. In this case it
>> is one of the forking computations reaching a goal, there is no
>> communication at all within processes.
>
> And yet the "arbiter" knows when the goal is reached, and
>each process must know which part of the computational tree it is
>following [else two clones must do identical computations]. Let's
>carry on ...
No. The arbiter sees that a computation path has finished in an accepting
state (the arbiter is an AND gate).
>> Nope. Think about it as if there was an arbiter at the end of all
>> computation paths. You don't have to communicate to your siblings the fact
>> that you have found a satisfying tour, the arbiter declares you the
>> "winner" so to speak.
>
> Fine. But in this case, if there is no satisfying tour, then
>within [known and bounded, for HC] polynomial time the arbiter knows
>there is no winner and hence that this is a "no" instance. And you
>are saying rather more than "You don't have to communicate ..."; you
>*must* not communicate. If the arbiter knows the answer, why can't
>we? And *how* does the arbiter know? You can certainly define
>formalisms in which this works, but it is taking us further and further
>away from familiar ground.
Which brings up a different question. IS NP the really distinguished class
or should we be looking and studying NP \intersection co-NP, which
is more naturally defined?
Alex
--
Alex Lopez-Ortiz alop...@unb.ca
http://daisy.uwaterloo.ca/~alopez-o Assistant Professor
Faculty of Computer Science University of New Brunswick
Matt Timmermans
Dr A. N. Walker wrote in message <34FAA8...@maths.nott.ac.uk>...
>Matt Timmermans wrote:
>[A]
>> problem is in NP if it can be true instances can be _proven_ to be true
in
>> P-time by a process that can make infinitely lucky guesses, or can fork
>> itself to follow two separate paths simultaneously.
>
> This is sort-of true, but misleading. In the "forking" model,
>you must specify that one of the forks manages to prove the instance
>without reference to what the other forks do. This differs from what
>the "man on the Clapham omnibus" might expect, given the way in which
>real-world processes can communicate.
Well, yes, this is a "many-worlds" type of forking, which physics students
would get easily. There is no communication between the forked processes,
and they don't return information to the caller, unless the caller makes a
guess as to which individual process it wants a return value from, or forks
to accept values from all processes.
I find the absolute equivalence of forking and guessing, from the point of
view of any process-instance, quite attractive. Together they form a good
model of non-determinism, which is much more valuable than having a
real-world constructible model of an NDTM that proves the question, given
the appropriate extra input. An understanding of non-determinism gets you
quickly through all the acronyms beginning with "N".
Dr A. N. Walker
Alex Lopez-Ortiz wrote:
> No. The arbiter sees that a computation path has finished in an accepting
> state (the arbiter is an AND gate).
OK, but *why* can it not equally see that it has finished
in a non-accepting state [or is still going after a pre-determined
polynomial bound]? *Why* is it an AND gate rather than an OR gate
or an "operating system" [like Unix!] that can monitor the success
or failure of processes when they terminate? [These are rhetorical
questions!]
This started out as a question about pedagogy. In "your"
model, we started out with a simple concept [imagine that processes
can "fork" without limit, then the problem is in NP if, for "yes"
instances, one of the branches succeeds in polynomial time]. But
when the bright students start picking at it, we are forced to say
that although this is a very powerful [exponentially large] computer,
we're not going to allow it to do all sorts of things that real PCs
can do, and we have to resort to a much more formal definition,
which is driven by the need to capture what the rest of us mean by
NP-ness rather than by natural features of the model. To me, that's
a sign that the pedagogy is wrong.
> Which brings up a different question. IS NP the really distinguished class
> or should we be looking and studying NP \intersection co-NP, which
> is more naturally defined?
These may be the same thing, of course! The intersection
may be more naturally defined, but sadly it contains only one
problem worth discussing [PRIME/COMPOSITE]. NP may be artificial,
and I have to ask the students to bear with it for a while, but then
we get to the house of cards built up from SAT, 3SAT, VC, HC, TSP,
CLIQUE and the rest, and at least the problems are interesting. And
I'm open to correction, but I think the "natural" interpretation of
"your" model for NP would compute a *superset* of NP *\union* co-NP,
perhaps even EXPTIME, which in turn is more naturally computed quite
directly by taking exponentially long over it.
Jaap-Henk Hoepman
alop...@daisy.uwaterloo.ca (Alex Lopez-Ortiz) writes:
> I would like to hear about other people's experience in this regard.
> Do you teach NDTM as guessing or a computational tree? Did you learn
> NDTM as guessing or computational tree? Was it difficult to understand
> the concept of nondeterminism at the time?
Personally, I like to think of NP to be the class of problems where a solution
to an instance of the problem can be verified in polynomial time by a classical
algorithm. Talking about computing the solution to such a problem is
problematic, because non-deterministic machines just do not exist.
Regards,
Jaap-Henk
--
Jaap-Henk Hoepman | "Yes, we've eaten off the silver
Email: j...@innocent.com | (when even food was against us)!"
URL: http://www.xs4all.nl/~jhh | Nick Cave
PGP ID: 0xF52E26DD Fingerprint: 1AED DDEB C7F1 DBB3 0556 4732 4217 ABEF
Daniel A. Jimenez
In article <34F16CA0...@malihh.high-performance.de>,
Carsten Lutz <c...@malihh.high-performance.de> wrote:
>Moin, folx !
>
>I have a problem which should be easy to solve:
>
>I am wondering about the NP =? co-NP problem. As I understand, it is yet
>unknown if the equality holds. I don't really understand this. Let's
>take
>SAT as as an example for a problem in NP. The problem is ``is a boolean
>formula f satisfiable ?''. The Negation if SAT ( let's call it nSAT ) is
>then ``is a boolean formula f unsatisfiable ?''.
>
>If I don't miss anything, then you can just negate the answer of SAT to
>get an answer for nSAT. You could also apply this argument to all other
>Entscheidungsproblems. But in this case there would be no NP =? co-NP
>problem.
>
>What am I missing ? I'm sure it's pretty simple.
That's a good question. The answer lies in looking at exactly what it
means for a language to be in NP.
From the FAQ list for comp.theory:
-----
NP is the class of decision problems for which we can check solutions
in polynomial time.
Definition: NP is the class of decision problems (languages)
L such that there is a polynomial time function f(x,c) where
x is a string, c is another string whose size is polynomial
in the size of x, and f(x,c)=True if and only if x is in L.
-----
So there must be a poly-sized "certificate" c that proves that a string is
in a certain language. For the problem of SAT, the certificate is just a
satisfying assignment. What is the certificate for nSAT? Maybe there
isn't one.
Of course, your question is valid. Put another way, if we have a function
A(x) that returns True iff x is in SAT, why not just construct a new
function B(x) = not A(x) that returns True iff x is in nSAT?
Ok, let's do that. Then there are two possibilities:
1. P = NP.
Then there exists an algorithm for B that runs in polynomial time.
A recording of its steps, like the traces that some debuggers provide,
can serve as a poly-sized certificate for x being in nSAT. Since P = NP,
co-NP = NP also (since P is closed under complementation), so that's no
surprise.
2. P != NP.
Then any algorithm for A (and thus B) must run in exponential (or at least
superpolynomial) time. An invokation of A returning True can produce a
poly-sized certificate, so SAT is in NP. But an invokation of A returning
False can produce no certificate, only an apology. If B wants a certificate,
it may use a recording of the steps A took in failing to prove x is in SAT,
but this recording must be of superpolynomial size so doesn't qualify nSAT
for NP. It isn't known whether there is a poly-sized certificate for nSAT or
not.
Hope this helps...
--
Daniel Jimenez djim...@dryad.cs.utsa.edu
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
Daniel A. Jimenez
Carsten Lutz
Moin, folx !
I have a problem which should be easy to solve:
I am wondering about the NP =? co-NP problem. As I understand, it is yet
unknown if the equality holds. I don't really understand this. Let's
take
SAT as as an example for a problem in NP. The problem is ``is a boolean
formula f satisfiable ?''. The Negation if SAT ( let's call it nSAT ) is
then ``is a boolean formula f unsatisfiable ?''.
If I don't miss anything, then you can just negate the answer of SAT to
get an answer for nSAT. You could also apply this argument to all other
Entscheidungsproblems. But in this case there would be no NP =? co-NP
problem.
What am I missing ? I'm sure it's pretty simple.
greetinx,
Carsten
--
* Carsten Lutz, Hamburg, GER /
c...@malihh.high-performance.de *
* Voice Tel.: +49 40
85322368 *
* PGP: finger me for my public key. key size:1024 key
ID:0A5545C9 *
* fingerprint: 37 AA 47 09 2C F7 7E A0 04 57 55 33 FE 7F 9D
73 *
* "I don't mind going nowhere as long as it's an interesting path" -
unknown *
Carsten Lutz
Daniel A. Jimenez wrote:
> [...]
> That's a good question. The answer lies in looking at exactly what it
> means for a language to be in NP.
>
> From the FAQ list for comp.theory:
> -----
> NP is the class of decision problems for which we can check solutions
> in polynomial time.
>
> Definition: NP is the class of decision problems (languages)
> L such that there is a polynomial time function f(x,c) where
> x is a string, c is another string whose size is polynomial
> in the size of x, and f(x,c)=True if and only if x is in L.
> -----
that are accepted by a non-deterministic TM in polynomial time创. So
these two definitions seem to be equivalent. Why ? I suspect the
following:
1. Let there be a certificate c that can be checked in polynomial time.
Then define a NTM as follows: Nondeterministically pick a string
from the space of all potential certificates and check if it is a
certificate ( can be done in polynomial time ).
The NTM will pick a string that in fact is a certificate if such a
string exists. This NTM obviously accepts the language in question
in polynomial time.
2. Let there be a NTM which accepts a language L in polynomial time. For
any word from L, its trace is of polynomial size. The same steps can
be
performed by an appropriate deterministic TM in polynomial time so
the trace serves as a certificate.
Is this correct ? ( Hope the above is not too confused )
[..very.helpful.explanations.deleted..]
Thank you for your detailed answer. It covered exactly the points that I
was
unsure about.
Daniel Jimenez
In article <34F30843...@malihh.high-performance.de>,
Carsten Lutz <c...@malihh.high-performance.de> wrote:
>Daniel A. Jimenez wrote:
>> [stuff deleted]
>> Definition: NP is the class of decision problems (languages)
>> L such that there is a polynomial time function f(x,c) where
>> x is a string, c is another string whose size is polynomial
>> in the size of x, and f(x,c)=True if and only if x is in L.
>I just read the FAQ. Hmm. The usual definition for NP is ``The languages
>that are accepted by a non-deterministic TM in polynomial time´´.
Funny how it said just what I wanted it to say :-). I find the notion
of a non-deterministic Turing machine a somewhat awkward way to explain NP.
A polynomial-time function is easy to explain to someone ("oh, you just mean
a [insert favorite computer language here] subroutine that runs in O(n^k)
for some constant k") than a non-deterministic Turing machine ("let's see,
there's a tape, waitaminute, two tapes, and one of them happens to have the
right answer on it? huh?"). _Algorithmics_ by Brassard and Bratley (the
book closest to my hand that mentions NP) takes roughly the same approach in
its definition.
>So
>these two definitions seem to be equivalent. Why ? I suspect the
>following:
>
>1. Let there be a certificate c that can be checked in polynomial time.
> Then define a NTM as follows: Nondeterministically pick a string
> from the space of all potential certificates and check if it is a
> certificate ( can be done in polynomial time ).
> The NTM will pick a string that in fact is a certificate if such a
> string exists. This NTM obviously accepts the language in question
> in polynomial time.
Yes.
>2. Let there be a NTM which accepts a language L in polynomial time. For
> any word from L, its trace is of polynomial size. The same steps can
>be
> performed by an appropriate deterministic TM in polynomial time so
> the trace serves as a certificate.
>
>Is this correct ? ( Hope the above is not too confused )
Hmm, sort of. An NDTM a la Garey & Johnson is just a DTM with an extra tape.
The extra tape is initially written with some non-deterministically chosen
bits, then the DTM part does its poly-time computation. If any configuration
of the extra tape causes the DTM to accept the input string, then that
configuration *itself* is the certificate. There's no need to resort to a
trace of the machine to extract the certificate.
--
Daniel Jiménez djim...@bluebonnet.uthscsa.edu
Daniel Jimenez
In article <6d1601$4...@news.sns-felb.debis.de>,
Matthias Oberlaender <oberl...@dbag.ulm.DaimlerBenz.COM> wrote:
>In <yfura4s...@mpii02045.mpi-sb.mpg.de> Juergen Stuber wrote:
>> [good stuff deleted]
>> This is not allowed. When you negate answers, you do not stay in NP.
>No, you can't say that (not yet :-). That's indeed the unresolved question:
>Do we stay or don't we? i.e. is NP != co-NP or is NP = co-NP. But what is an
>intuitive reason against the latter, or at least against the "obvious", but
>fallacious equivalence? This is Carsten's question, I guess. In propositional
>logic there is a perfect symmetry between TRUE and FALSE. But in one way or
>another this symmetry is lost when we talk about satisfiability. Where has
>it gone?
Let's look at four problems:
CNF-SAT (conjunctive normal formula satisfiability):
Is there an assignment that causes the CNF to be true?
This is NP.
CNF-NSAT (CNF unsatisfiabilty):
Is there no assignment that causes the CNF to be true?
This is co-NP.
DNF-TAUT (disjunctive normal formula tautology):
Is there no assignment that causes the DNF to be false?
This is co-NP (proof: suppose x is CNF. apply DeMorgan, get
not (x) in DNF. DNF-TAUT for not(x) is CNF-NSAT for x)
DNF-NTAUT (DNF not a tautology):
Is there an assignment that causes the DNF to be false?
This is NP (proof is similar, use CNF-SAT)
Now, here's the symmetry you may be looking for:
(please excuse the ASCII graphics, I like pictures :-)
______ ______
/ \ / \
/CNFSAT \ DNFTAUT\
/ / \ \ Of course, with the standard
/ / \ \ disclaimer "if P != NP"
/ NP / P \ co-NP \
\ \ / /
\ \ / /
\ \ / /
\DNFNTAUT\CNFNSAT /
\______/ \______/
>[more good stuff deleted]
Daniel Jimenez
In article <EoxzA...@undergrad.math.uwaterloo.ca>,
Alex Lopez-Ortiz <alop...@daisy.uwaterloo.ca> wrote:
>In article <6cvcgb$i2g$1...@cosmos.uthscsa.edu>,
>Daniel Jimenez <djim...@bluebonnet.uthscsa.edu> wrote:
>>In article <34F30843...@malihh.high-performance.de>,
>>Carsten Lutz <c...@malihh.high-performance.de> wrote:
>>>I just read the FAQ. Hmm. The usual definition for NP is ``The languages
>> I find the notion of a non-deterministic Turing machine a somewhat
>> awkward way to explain NP. A polynomial-time function is easy to
>>right answer on it? huh?"). _Algorithmics_ by Brassard and Bratley (the
>>book closest to my hand that mentions NP) takes roughly the same approach in
>>its definition.
>
>machines I've found that most concepts are more redily grasped if
>we think of computation paths for NDTMs as full trees in which
>both non-deterministic choices are taken and as long as at least one of
>the paths accepts, the NDTM accepts.
>I would like to hear about other people's experience in this regard.
>Do you teach NDTM as guessing or a computational tree? Did you learn
>NDTM as guessing or computational tree? Was it difficult to understand
>the concept of nondeterminism at the time?
(I'm not other people but I'll still respond :-)
My approach is motivated by a desire to reduce the hocus-pocus aspect
of non-determinism. When I first learned it, it sounded like a model
of computation where a machine could just fork a copy of itself and
both would explore different parts of the solution space. This led
me to various misconceptions that were only really fixed when I read
Garey & Johnson. I think a similar train of thought may have led to the
question that started this thread.
I'm teaching an undergraduate Algorithms course this semester (with
CLR, not Brassard) and I'll use the polynomial certificate approach.
I'll bring up NDTMs with guessing only after I'm sure the students
get the basic idea of NP (and are beyond thinking it really means
"non-polynomial", the pet peeve of computer scientists everywhere :-).
In a different course like Theory of Computation, I would handle it
differently, but of course spell out very meticulously exactly what an
NDTM is so no one gets the wrong idea.
Matthias Oberlaender
> > > In article <34F16CA0...@malihh.high-performance.de>,
> > > Carsten Lutz <c...@malihh.high-performance.de> wrote:
> > > >
> > > >I have a problem which should be easy to solve:
> > > >
> > > >I am wondering about the NP =? co-NP problem. As I understand, it is
yet
> > > >unknown if the equality holds. I don't really understand this. Let's
> > > >take
> > > >SAT as as an example for a problem in NP. The problem is ``is a
boolean
> > > >formula f satisfiable ?''. The Negation if SAT ( let's call it nSAT )
is
> > > >then ``is a boolean formula f unsatisfiable ?''.
> >
> > formulas in general, but only to those in conjunctive normal form.
>
> This doesn't make a difference. You can translate any boolean formula
> into a 3SAT formula with linear overhead, preserving satisfiability:
>
> - Introduce a new propositional variable for each subformula.
> - Add equivalences on these new propositional variables that
> express the relation between a formula and its immediate subformulas.
> Convert these equivalences to CNF. The size of these CNFs is bounded
> by a constant.
> - Add a the propositional variable corresponding to the whole formula
> as a unit clause, to state that the whole formula must be true.
>
> See e.g. Schöning, Theoretische Informatik kurzgefaßt.
>
> > > >If I don't miss anything, then you can just negate the answer of SAT
to
> > > >get an answer for nSAT.
>
No, you can't say that (not yet :-). That's indeed the unresolved question:
Do we stay or don't we? i.e. is NP != co-NP or is NP = co-NP. But what is an
intuitive reason against the latter, or at least against the "obvious", but
fallacious equivalence? This is Carsten's question, I guess. In propositional
logic there is a perfect symmetry between TRUE and FALSE. But in one way or
another this symmetry is lost when we talk about satisfiability. Where has
it gone?
> If you try to construct a TM to accept the negation, you will notice
> that you need a TM that accepts only if all computations accept.
> In NP you have a TM that accepts if one computation accepts
> (everything polynomially bounded, of course).
Again what I said in my previous post: You can't easily convert from CNF to
DNF because this would immediately solve all problems: The DNF of an
unsatisfiable formula is empty, i.e. does not have a single term. Right? So
the following algorithm would do:
Test for membership in nSAT:
1. Convert your formula to DNF.
2. If the set of resultant terms is emtpy return TRUE else return YES.
As an aside: The SAT problem does neither deal with the complexity of
evaluating single values of a boolean formula (which is always easy for
polynomially bounded formulas) nor for all possible input values (which
requires exponential time). In its deeper and rich sense it tackles the
question of how certain structures, which are members of rather freely
definable equivalence classes, can be converted into each other efficiently,
thus proving equivalence. Incidentally, these structures may denote boolean
formulas in the eye of the beholder. But what he calls TRUE and what FALSE is
indeed totally irrelevant. And even more: it is also totally irrelevant
whether he perceives in such a structure an instance of the SAT problem, the
Hamiltonian path problem, a quadratic diophantine equation ... or an instance
ot whatever class has been proven to be NP-complete.
--
____ __ _/_/ .
( / / ( / / / /
=====================================================================
Matthias Oberlaender, Daimler-Benz AG, Research Center Ulm
FT3/AB (Information Technology)
Wilhelm-Runge-Str. 11, P.O. Box 2360, 89013 Ulm, Germany
Phone: +49 731 505 2354 Fax: +49 731 505 4113
Email: oberl...@dbag.ulm.DaimlerBenz.COM
=====================================================================
Juergen Stuber
If you try to construct a TM to accept the negation, you will notice
that you need a TM that accepts only if all computations accept.
In NP you have a TM that accepts if one computation accepts
(everything polynomially bounded, of course).
Jürgen
--
Jürgen Stuber <jue...@mpi-sb.mpg.de>
http://www.mpi-sb.mpg.de/~juergen/
Alex Lopez-Ortiz
In article <6cvcgb$i2g$1...@cosmos.uthscsa.edu>,
Daniel Jimenez <djim...@bluebonnet.uthscsa.edu> wrote:
>Carsten Lutz <c...@malihh.high-performance.de> wrote:
>
>>I just read the FAQ. Hmm. The usual definition for NP is ``The languages
>>that are accepted by a non-deterministic TM in polynomial time.
>
> I find the notion of a non-deterministic Turing machine a somewhat
> awkward way to explain NP. A polynomial-time function is easy to
> explain to someone than a non-deterministic Turing machine ("let's see,
>there's a tape, waitaminute, two tapes, and one of them happens to have the
>right answer on it? huh?"). _Algorithmics_ by Brassard and Bratley (the
>book closest to my hand that mentions NP) takes roughly the same approach in
>its definition.
Indeed. Moreover, when it comes time to introduce nondeterministic
machines I've found that most concepts are more redily grasped if
we think of computation paths for NDTMs as full trees in which
both non-deterministic choices are taken and as long as at least one of
the paths accepts, the NDTM accepts.
I would like to hear about other people's experience in this regard.
Do you teach NDTM as guessing or a computational tree? Did you learn
NDTM as guessing or computational tree? Was it difficult to understand
the concept of nondeterminism at the time?
Matthias Oberlaender
> In article <34F16CA0...@malihh.high-performance.de>,
> Carsten Lutz <c...@malihh.high-performance.de> wrote:
> >Moin, folx !
> >
> >I have a problem which should be easy to solve:
> >
> >I am wondering about the NP =? co-NP problem. As I understand, it is yet
> >unknown if the equality holds. I don't really understand this. Let's
> >take
> >SAT as as an example for a problem in NP. The problem is ``is a boolean
> >formula f satisfiable ?''. The Negation if SAT ( let's call it nSAT ) is
> >then ``is a boolean formula f unsatisfiable ?''.
This is not correct! The classical SAT problem does not refer to boolean
formulas in general, but only to those in conjunctive normal form.
> >
> >If I don't miss anything, then you can just negate the answer of SAT to
> >get an answer for nSAT. You could also apply this argument to all other
> >Entscheidungsproblems. But in this case there would be no NP =? co-NP
> >problem.
> >
> >What am I missing ? I'm sure it's pretty simple.
>
The crux (and possibly the solution to your problem) is the fact that the
negation of a CNF formula does not preserve its CNF property. In essence the
NP vs. co-NP problem is closely related to the problem of converting a
formula from CNF to DNF, or vice versa, for which no polynomial time
algorithm is known.
Hope I'm correct.
Dr A. N. Walker
Alex Lopez-Ortiz wrote:
> I would like to hear about other people's experience in this regard.
> Do you teach NDTM as guessing or a computational tree?
Oh, as guessing. Pedagogically it makes much more sense.
I think the people who witter on about "accepting languages" and
"certificates", etc, are just trying to make CS/Maths look difficult.
NP is the class of decision problems that can be solved in polynomial
time for "yes" instances if your computer happens to be "lucky". See
http://www.maths.nott.ac.uk/personal/anw/G12FCO/lect10.html
for how I actually do it with our students. [This is from the middle
of a module for second-year undergraduates, mostly specialising in
maths. They're pretty bright, but have rather little CS background
at this stage.]
It is then "obvious" that, eg "is n composite?" and "does
this graph have a Hamiltonian circuit?" are in NP, and the asymmetry
between "yes" and "no" answers is also evident.
Of course, if you're going to do research in this area, you
need to know and use a much more formal language. But not for
teaching.
> Did you learn
> NDTM as guessing or computational tree? Was it difficult to understand
> the concept of nondeterminism at the time?
I learned it from Garey and Johnson. I don't think anyone
could claim that G&J is light bed-time reading! The *concept* of
non-determinism isn't hard; but its formalisation is.
Alex Lopez-Ortiz
In article <34F58D...@maths.nott.ac.uk>,
>> I would like to hear about other people's experience in this regard.
>> Do you teach NDTM as guessing or a computational tree?
>
> Oh, as guessing. Pedagogically it makes much more sense.
>I think the people who witter on about "accepting languages" and
>"certificates", etc, are just trying to make CS/Maths look difficult.
Just to clarify, a computational tree does not involve certificates
or accepting languages.
In the computational tree, whenever a guess (in the standard sense) is made,
the program forks (in the unix sense) and explores the option where the bit
guessed is 0 and the one where it is 1.
That is, if you look at the trace of a deterministic computation, you get
a path, the trace of a nondeterministic computation is a tree with the
branches occurring in nondeterministic transitions.
>NP is the class of decision problems that can be solved in polynomial
>time for "yes" instances if your computer happens to be "lucky". See
>
> http://www.maths.nott.ac.uk/personal/anw/G12FCO/lect10.html
Couldn't we solve unsolvable problems if the computer is lucky? my
students often ask...
>for how I actually do it with our students. [This is from the middle
>of a module for second-year undergraduates, mostly specialising in
>maths. They're pretty bright, but have rather little CS background
>at this stage.]
>
> It is then "obvious" that, eg "is n composite?" and "does
>this graph have a Hamiltonian circuit?" are in NP, and the asymmetry
>between "yes" and "no" answers is also evident.
>
> Of course, if you're going to do research in this area, you
>need to know and use a much more formal language. But not for
>teaching.
>
>> Did you learn
>> NDTM as guessing or computational tree? Was it difficult to understand
>> the concept of nondeterminism at the time?
>
> I learned it from Garey and Johnson. I don't think anyone
>could claim that G&J is light bed-time reading! The *concept* of
>non-determinism isn't hard; but its formalisation is.
Interesting observations. I would like to hear even more opinions.
(I've received a few over e-mail) Keep 'em coming...,
>
>--
>Andy Walker, Maths Dept., Nott'm Univ., UK.
>a...@maths.nott.ac.uk
James Foster
In article <Ep028...@undergrad.math.uwaterloo.ca> alop...@daisy.uwaterloo.ca (Alex Lopez-Ortiz) writes:
From: alop...@daisy.uwaterloo.ca (Alex Lopez-Ortiz)
Newsgroups: comp.theory
Interesting observations. I would like to hear even more opinions.
(I've received a few over e-mail) Keep 'em coming...,
There are very many equivalent definitions of NP (and co-NP). It
shouldn't be too hard to come up with about a dozen.
in the SIGACT News about a year ago there was a wonderful one-page
summary of ways to prove or disprove that P=NP...very funny in a
perverse sort of way.
NP is the class of problems you can solve in polynomial time if you
have an infinite supply of processors (and finding the solution on ONE
processor is solving the problem).
NP is the class of problems you can solve if you can always make a
binary decision about which computation path to follow...and always be
right.
NP is the class of problems for which you can verify that a solution
to a given instance is correct in polynomial time.
NP is the class of problems for which each instance has a "small"
witness (polynomial in the size of the instance) for that it is a
"yes" instance.
NP is the class of of problems you could solve in polynomial time, if
only you could recognize quickly whether or not an arbitrary boolean
formula were satisfiable. (Cook)
NP is the class of problems for which there is a short certificate
(poly in size of the instance) which can be verified with high
confidence by a polynomial time verifier which uses a logarithmic (in
the instance size) number of random bits and checks a constant number
of bits. (pcp characterization)
NP is the class of problems which can be verified in an interactive
game where one player is polynomial time and the other is
computationally unrestricted. (Restricted IP approach)
NP is the class of problems recognizable in polynomial time on a
nondeterministic polynomial time machine. <yawn>
NP is the class of problems expressible with a single second order
existential quantifier over unquantified second order predicates
(Fagin)
NP is the class of problems expressible with a single existential
variable with a polynomial (in the length of the free variable) bound
on the quantified variable and a p-time computable predicate. (Wrathall)
There are game-based definitions, circuit based definitions, automata
based ones, logic based ones, model theoretic ones, ....
And they're all equivalent.
In my humble opinion, the "classical" definition in terms of Turing
machines is just about the least interesting and most artificial of
them all!
--
James A. Foster email: fos...@cs.uidaho.edu
Laboratory for Applied Logic Dept. of Computer Science
University of Idaho http://www.cs.uidaho.edu/~foster
pgp key available at: ftp://ftp.cs.uidaho.edu/pub/foster/pgp-key.asc
Matthias Oberlaender
There is quite a common classification of boolean formulas into three types:
1. contingent formula (i.e. those which sometimes yield true and sometimes
false over all variable assignments)
2. tautologies (those which always yield true)
3. contradictions (those which always yield false)
Distinguishing between CONTRADICTION and TAUTOLOGY is not the matter. They
may be converted into each other by simple negation. However, we want to
distinguish the class CONTINGENT from the others. Now, let's see:
Assume CNF representation of formulas: Then TAUTOLOGY can be recognized
easily. Thus the problem of distinguishing CONTINGENT from CONTRADICTION
remains.
Assume DNF representation of formulas: Then CONTRADICTION can be recognized
easily. Thus the problem of distinguishing CONTINGENT from TAUTOLOGY remains.
Perfect symmetric treatment of "True" and "False" is regained (IMHO) if we
abstract from CNF and DNF representation and simply ask:
a) Is this boolean formula contingent?
b) Is this boolean formula not contingent?
So it's decision problem a) for CONTINGENT which is NP. And consequently, by
definition, it's NOT-CONTINGENT = CONTRADICTION+TAUTOLOGY which is co-NP.
So we get the new picture
______ ______
/ \ / \
/CONTING.\ TAUTOL.\
/ / \ CONTRA.\ Of course, with the standard
/ / \ \ disclaimer "if P != NP"
/ NP / P \ co-NP \
\ \ / /
\ \ / /
\CNFSAT \ /CNFNSAT /
\DNFNTAUT\DNFNTAUT/
\______/ \______/
JDPeh
Your four problems indirectly raise an important point, often
neglected. NP (satisfiability) and coNP (unsatisfiability) are
special cases of a more general PSpace problem. So, if I
may divert the discussion a bit, consider your four problems
to be special cases of Quantified Boolean Formula.
A QBF looks like:
Ax1 Ex2 ... Axn: P(x1,...,xn). Is the sentence True?
where the prefix is a list of n quantifiers (All, Exists) on the
boolean variables x1...xn, and P is a propositional expression
over the variables x1...xn. See page 173 of Garey and Johnson for
details. A satisifiability question has n Exists quantifiers,
and a tautology question has n All quantifiers.
It could be that an efficient solution (if any) to NP and coNP
uses quantified boolean subformulae, on subproblems; that is,
to understand how hard (or how to solve) NP problems are, you may
first have to consider how hard QBF on subproblems is. If NP is
hard, it might be because the subproblems are hard; and likewise,
if it is easy, it would be because the subproblems are easy. Just
because the top level problem has n Existential quantifiers, that
does not mean that the subproblems are so simply described, in an
efficient solution.
The rest of this message is a rather dense summary of some new ideas
about QBFs. When posting comments about it, I suggest deleting all
but the relevant section, instead of copying the entire 11k message.
Apologies for the lack of papers and refs.
--- Another look at QBF:
There are several surprising features of QBFs that are not very well
known. They may lead to a new way of looking at QBFs. The ideas
come from considering a general form for QBF:
q1 q2 ... qn P(x1,...,xn)
where the qj encode quantifiers for variables xj. By treating the
qj as simple boolean variables(!!), some interesting relationships
between P(x1,...,xn) and the qj's can be discovered!
--- Two intriguing ideas
Using the generalized representation above, observations about
the relationship between the qj's "space" and the xj's "space"
can be made.
The first major idea is the counting theorem, that equates the
number of satisfying assignments of a formula P to the number of
distinct, valid, quantified sentences of P. The theorem is called
#P=#Q. This equality between "number of valid assignments to a
satisfiability problem P" and "number of valid QBF sentences of P"
demonstrates an exciting and fundamental relationship between
PSpace and NP.
The second idea, loosely following from the first, is the fact that there
exists a boolean expression Q, which encodes all the valid quantifications
of the original boolean expression P!
Use the variables q1...qn, to encode the space of all quantification
sentences of P, where qj corresponds to a boolean variable, meaning
"All xj", or, "Exists xj". Clearly, some assignments to the qj's will be
valid, and some won't. And, just as clearly, there is certainly a boolean
expression over the qj's that accepts exactly and only those assignments
that correspond to valid quantifications.
So, the expression Q, a pure boolean expression, representing all valid QBF
sentences for P, clearly exists! This surprising result is a significant
leap forward in understanding QBFs. The fact that the expression Q exists
also demonstrates an exciting and fundamental relationship between PSpace
and NP.
Once you have the expression Q, via some involved computation, you
can check any particular quantification q very simply: just check q (an
assignment to q1..qn) in the expression Q. The fact that Q exists (when
P is satisfiable) is not in doubt, just its size, and the difficulty of
constructing it. But, once you have it, ANY of the 2^n possible
quantifications of P may be checked in time linear in Q !!
The following goes into some detail on these two ideas.
--- Theorem: #P = #Q
The number of satisfying assignments (#P) to a boolean expression P
is identical to the number of valid quantified sentences (#Q)
over the expression P, given a fixed variable ordering.
The proof is a natural induction on the number of boolean variables
in the expression P. It was first proven by Ranaan Fraer, last July,
in this newsgroup.
--- What are quantifications?
Example (1):
(All a)(Exists b) ((a and b) and (-a or -b))
The problem of checking any particular quantified sentence for
validity is called QBF; the problem is in a complexity class
called PSpace-complete.
As a simple example (2) to demonstrate the truth of the above theorem,
use the boolean expression (a and b). The only valid quantified sentence
is (Ea)(Eb) (a and b), given the fixed variable ordering. It has 1
satisfying assignment, and 1 valid quantified sentence, obeying the theorem.
Another example (3), use the boolean expression (a or b);
the only quantification that does not work is (Aa)(Ab)(a or b), out
of four possible quantifications.
Example (1) above is a valid quantified sentence. Since there are
2 satisfying assignments to the expression body, there must be another
valid quantification:
(Exists a)(Exists b) ((a or b) and (-a or -b))
Unsatisfiable formulae, of course, have no valid assignment and
no valid quantification. Tautologies, similarly, have 2^n valid
assignments and 2^n valid quantifications, with a fixed variable
ordering.
--- "Where" is the theorem?
The problem of counting valid assignments to a boolean expression
is in a class called number-P Complete. QBF is a PSpace complete
problem. I don't know if there is a name for the problem of
counting valid distinct quantifications, but I call the new
complexity class #Q, analogous to the #P complexity class.
The theorem occurs right at the top of the polynomial hierarchy.
It equates two previously disparate sections of the polynomial
hierarchy, the number problem versions of PSpace and NP.
---- Constructing Q from P
One useful area of research is the construction of Q from P. It
is a sort of transform, and the above #P=#Q theorem may help in the
construction of Q. At the least, the theorem provides a way of
checking partial correctness of the construction.
The idea is to construct a boolean expression Q that represents
all valid quantified sentences for a particular expression body.
Once constructed, any quantified sentence can be checked merely by
checking an assignment in Q. The implications are significant. If
the size of Q can be bounded by a polynomial function of the size
of P, then PSpace = NP may follow directly!
At this time, it is unproven that Q may always be made polynomial
in the size of P, but empirical evidence (small cases only) suggests
that it may be true. At least, it is not obviously false!
Another nice property of Q is monotonicity. To see this, 2cnf formulae
are good to explore, since the construction of the corresponding Q
formula from a 2cnf expression P is strictly polynomial.
Currently, I am investigating constructing Q for kcnf by merging
solutions to smaller constructions. While most theoreticians would
expect an efficient construction to be unlikely, it's worth trying.
--- Summary
To my knowledge, the problem of counting valid quantifications to a
boolean expression is previously uninvestigated. However, the idea
is a natural extension of QBF.
In most chapters and books about NP, the discussion stops right
at the introduction of the QBF problem. Some do not even introduce
the counting problem, #P. ( I suppose that's the point at which
everyone's eyes glaze over...but, really, its very simple, after
just 10 years of study :)
The equivalence between the #P and #Q classes, and the existence
of the expression Q lead to the exciting possibility that PSpace
is equivalent to NP. That is not yet proven, but is plausible.
One might argue whether that means PSpace is easier than previously
thought, or, that NP is just as hard as anything in PSpace. However,
the ideas are worthy of theoretical investigation. For now, I am
investigating the "PSpace easier" angle, as success, if possible, should
be easy to demonstrate!
---
I really should write a paper about the above ideas, but frankly, I
would rather explore their implications. Not the normal way of
"publishing" new results, but until I get around to a paper, posts
like this will have to do. In any case, if you get into this stuff,
a word of advice: it can get intense, so make an explicit point to
"smell the roses", for your own sake. Seriously, I have found that
prolonged, deep study and programming on this problem can muddle one's
reality a little bit, as those who know me already understand. There
might be more to this problem than meets the eye. So, hesitantly,
I encourage it's study, if that makes any sense.
If there are other researchers who are actively interested
in solving QBFs, I would appreciate any pointers. Please
forward this message to those who would be interested.
If either of the basic ideas ( #P=#Q, the existence of the expression Q )
needs further explanation, please ask. I have some sample expressions
from which Q has been constructed, including some 2CNF, 3CNF,
and a 4 pigeons in 4 holes example.
Thanks,
Dan Pehoushek
Matt Timmermans
Alex Lopez-Ortiz wrote in message ...
>I would like to hear about other people's experience in this regard.
>NDTM as guessing or computational tree? Was it difficult to understand
>the concept of nondeterminism at the time?
My first introduction to nondeterministic computation came from NFAs.
Algorithms for converting NFAs to DFAs encode the superposition model, while
popular algorithms for running NFAs encode the lucky guess model, so both
models were available come NDTM time.
With both models, the hardest thing to appreciate the implications of was
that NDTMs can't say no. The difficulty went away once I realized that the
NDTM in an NP decision problem wasn't deciding, but proving, and that a
problem is in NP if it can be true instances can be _proven_ to be true in
P-time by a process that can make infinitely lucky guesses, or can fork
itself to follow two separate paths simultaneously. This highlights the
difference between NP and co-NP nicely, because everybody knows that the
inability to prove that a statement is true is not a proof that it is false.
Dr A. N. Walker
Alex Lopez-Ortiz wrote:
> >I think the people who witter on about "accepting languages" and
> >"certificates", etc, are just trying to make CS/Maths look difficult.
> Just to clarify, a computational tree does not involve certificates
> or accepting languages.
Yes; sorry, I failed to make my position clear. Many of the
people who post to this group [in particular] asking about NP and its
relatives are clearly struggling to understand the concept. Replies
that involve abstractions such as languages [etc] may be correct, but
they do not help the understanding. "Everyone" understands concepts
such as "computer", "program", "prints 'yes'", "random number", "luck"
etc., so they are useful concepts in explanations. But the language
of Garey and Johnson, or other formal books on computing, is not so
familiar, and it is part of what is causing the mental blockage in the
first place.
There are similar conceptual problems in areas such as Turing
machines, languages, grammars, and elsewhere. I find that students
are much more at ease with "TM == PC with pile of floppy discs [etc]"
than with "TM == set of quintuples blah blah", however important the
"correct" definition may be when you want to prove advanced theorems
about about TMs.
> Couldn't we solve unsolvable problems if the computer is lucky? my
> students often ask...
If you're lucky enough to solve the problem, then it wasn't
unsolvable in the first place [of course]. Put another way, a proof
of unsolvability implies that luck won't help. You will recall that,
before Wiles, Fermat's Last Theorem was often used as a potential
example of a "theorem" that might be unsolvable; but a *proof* of
unsolvability would prove that the result is true, for if it is false
then a lucky guess could establish a counterexample, so no such proof
can exist.
Alex Lopez-Ortiz
In article <34FAA8...@maths.nott.ac.uk>,
>you must specify that one of the forks manages to prove the instance
>without reference to what the other forks do.
Indded, you must define the termination condition. In this case it
is one of the forking computations reaching a goal, there is no
communication at all within processes.
> On the "forking" model, every time I get to a choice of routes
>I can fork off some children and send them off, one to each route. I
>then just wait for them to report success or failure. If any one of
>them reports success, I can report success to my parent; if they all
>report failure, then [in polynomial time!] I can report failure to my
>parent. So, in polynomial time, I can "prove" not only the "yes"
>instances, but also the "no" instances.
Nope. Think about it as if there was an arbiter at the end of all
computation paths. You don't have to communicate to your siblings the fact
that you have found a satisfying tour, the arbiter declares you the
"winner" so to speak. This is akin to ho #P, Maj-P and Parity-P are defined.
>You can prevent this only by preventing reporting to parents! But
>what sort of "computer" is it in which processes "know" whether they
>have succeeded or failed, and a success can be reported to the
>outside world but failure must be kept completely secret?
See above.
> So, in the "forking" model, we not only need an unrealistic
>model of computation in the first place [where do our exponentially-
>many processes fit in? do we not need exponentially much disc space
>and processor power?], but we also need to stop these processes from
>talking to each other. In other words, something that looks at first
>glance like a rather homely model starts to unravel. No wonder that
>people find it confusing. Pedagogically, it's all wrong.
My experience is that students have a hard time grasping the formal
idea behind guessing. While I think most would have no problem understanding
your Nothingam pub-crawl analogy (I like ti by the way), when it comes to
formally defining nondeterminism it just sounds to hocus-pocus to most.
Alex
--
Alex Lopez-Ortiz alop...@unb.ca
http://daisy.uwaterloo.ca/~alopez-o Assistant Professor
Faculty of Computer Science University of New Brunswick
Dr A. N. Walker
Matt Timmermans wrote:
[A]
> problem is in NP if it can be true instances can be _proven_ to be true in
> P-time by a process that can make infinitely lucky guesses, or can fork
> itself to follow two separate paths simultaneously.
This is sort-of true, but misleading. In the "forking" model,
you must specify that one of the forks manages to prove the instance
without reference to what the other forks do. This differs from what
the "man on the Clapham omnibus" might expect, given the way in which
real-world processes can communicate.
To see the difference, think about trying to do a Hamiltonian
pub-crawl around Nottingham. On the "lucky guess" model, I trust to
my luck, and set off round the pubs. I get back home having visited
every pub exactly once [hooray!] or else find myself in some pub for
the second time [boo!]. The "hooray" case establishes membership of
NP; but a "boo" could mean either that I was unlucky or that this
particular pub-crawl is impossible, and I can't tell, in general, in
polynomial time which of these has happened [unless P == NP].
On the "forking" model, every time I get to a choice of routes
I can fork off some children and send them off, one to each route. I
then just wait for them to report success or failure. If any one of
them reports success, I can report success to my parent; if they all
report failure, then [in polynomial time!] I can report failure to my
parent. So, in polynomial time, I can "prove" not only the "yes"
instances, but also the "no" instances. In this model, NP == co-NP.
You can prevent this only by preventing reporting to parents! But
what sort of "computer" is it in which processes "know" whether they
have succeeded or failed, and a success can be reported to the
outside world but failure must be kept completely secret?
So, in the "forking" model, we not only need an unrealistic
model of computation in the first place [where do our exponentially-
many processes fit in? do we not need exponentially much disc space
and processor power?], but we also need to stop these processes from
talking to each other. In other words, something that looks at first
glance like a rather homely model starts to unravel. No wonder that
people find it confusing. Pedagogically, it's all wrong.
Lucky guesses, on the other hand, work exactly the way you'd
expect them to. The concept is easy to explain [though its usefulness
isn't, until you get through NP-completeness and find that many useful
problems are NPC], and you don't have to keep referring back to Turing
machines, you can do it all with "real" programs for the PC.