Greetings,

Can someone give me an opinion as to whether the following proves that
the complement of HAMPATH is in NP?

Let HAMPATH := { <G,s,t> | G is a directed graph with a hamiltonian path from
			    s to t }

We know that HAMPATH is in NP. Also we know that the complement of HAMPATH
(we denote it by coHAMPATH) is in coNP. Now, we know that it is still
open as to whether coHAMPATH is in NP (cf. Sipser p. 243) (most researchers 
believe that it is not). 

Theorem: coHAMPATH is in NP
Proof:
Let M be the nondeterministic Turing machine (NTM) that decides HAMPATH. We 
design an NTM N that decides coHAMPATH as follows:

N=``On input <G,s,t>:
    1. Run M on input <G,s,t>
    2. If M accepts, reject. Otherwise, accept.''

If M accepts on input <G,s,t>, then <G,s,t> is in HAMPATH, ie, <G,s,t> is not
in coHAMPATH. If M rejects on input <G,s,t>, then <G,s,t> is not in
HAMPATH, ie, <G,s,t> is in coHAMPATH. Since there is an NTM that decides
coHAMPATH, it follows that coHAMPATH is in NP.

(qed)

Is there something wrong with my "proof"?

Thanks in advance,

Anthony

Anthony WIDJAJA wrote:

>Greetings,
>
>Can someone give me an opinion as to whether the following proves that
>the complement of HAMPATH is in NP?
>
>Let HAMPATH := { <G,s,t> | G is a directed graph with a hamiltonian path from
>			    s to t }
>
>We know that HAMPATH is in NP. Also we know that the complement of HAMPATH
>(we denote it by coHAMPATH) is in coNP. Now, we know that it is still
>open as to whether coHAMPATH is in NP (cf. Sipser p. 243) (most researchers 
>believe that it is not). 
>
>Theorem: coHAMPATH is in NP
>Proof:
>Let M be the nondeterministic Turing machine (NTM) that decides HAMPATH. We 
>design an NTM N that decides coHAMPATH as follows:
>
>N=``On input <G,s,t>:
>    1. Run M on input <G,s,t>
>    2. If M accepts, reject. Otherwise, accept.''
>
>If M accepts on input <G,s,t>, then <G,s,t> is in HAMPATH, ie, <G,s,t> is not
>in coHAMPATH. If M rejects on input <G,s,t>, then <G,s,t> is not in
>HAMPATH, ie, <G,s,t> is in coHAMPATH. Since there is an NTM that decides
>coHAMPATH, it follows that coHAMPATH is in NP.
>
>(qed)
>
>Is there something wrong with my "proof"
>
Indeed there is. A deterministic Turing machine accepts an input if and 
only if it does not reject it.

However, when we introduce nondeterminism, this duality between 
acceptance and rejection is lost.
A nondetermistic Turing machine accepts an input w if SOME computation 
on w halts in an accepting state, whereas it rejects an input w if ALL 
computations on w halt in a rejecting state.

In your "proof" above, the machine M may choose a computation such that 
<G,s,t> is rejected even though there is another possible computation 
which would cause <G,s,t> to be accepted. Thus, we cannot conclude that 
if M rejects <G,s,t>, then there is no hamiltonian path from s to t in G.

>  
>


-- 
Hans H�ttel                        | email: hans@cs.auc.dk
BRICS, Dept. of Computer Science   | WWW: http://www.cs.auc.dk/~hans/
Aalborg University                 | tel.: (+45) 96 35 88 88
Fredrik Bajersvej 7E               | fax: (+45) 98 15 98 89
9220 Aalborg �, DENMARK            | Fight spam!  http://www.cauce.org

To Anthony WIDJAJA <twidjaja@students.cs.mu.oz.au> wrote:
# Greetings,
# 
# Can someone give me an opinion as to whether the following proves that
# the complement of HAMPATH is in NP?
# 
# Let HAMPATH := { <G,s,t> | G is a directed graph with a hamiltonian path from
# 			    s to t }
# 
# We know that HAMPATH is in NP. Also we know that the complement of HAMPATH
# (we denote it by coHAMPATH) is in coNP. Now, we know that it is still
# open as to whether coHAMPATH is in NP (cf. Sipser p. 243) (most researchers 
# believe that it is not). 

This looks like homework...
Well, anyway:

 
# Theorem: coHAMPATH is in NP
# Proof:
# Let M be the nondeterministic Turing machine (NTM) that decides HAMPATH. We 
# design an NTM N that decides coHAMPATH as follows:
# 
# N=``On input <G,s,t>:
#     1. Run M on input <G,s,t>
#     2. If M accepts, reject. Otherwise, accept.''
# 
# If M accepts on input <G,s,t>, then <G,s,t> is in HAMPATH, 

Correct.

# ie, <G,s,t> is not in coHAMPATH.

Correct.
 
# If M rejects on input <G,s,t>, then <G,s,t> is not in HAMPATH, 

But M is non-deterministic.  
So what does it REALLY mean, if M rejects?

--Gerhard



# ie, <G,s,t> is in coHAMPATH. Since there is an NTM that decides
# coHAMPATH, it follows that coHAMPATH is in NP.
# 
# (qed)
# 
# Is there something wrong with my "proof"?
# 
# Thanks in advance,
# 
# Anthony


__________________________________________________________________
Gerhard J. Woeginger   http://wwwhome.cs.utwente.nl/~woegingergj/

> >Greetings,
> >
> >Can someone give me an opinion as to whether the following proves that
> >the complement of HAMPATH is in NP?
> >
> >Let HAMPATH := { <G,s,t> | G is a directed graph with a hamiltonian path from
> >			    s to t }
> >
> >We know that HAMPATH is in NP. Also we know that the complement of HAMPATH
> >(we denote it by coHAMPATH) is in coNP. Now, we know that it is still
> >open as to whether coHAMPATH is in NP (cf. Sipser p. 243) (most researchers
> >believe that it is not).
> >
> >Theorem: coHAMPATH is in NP
> >Proof:
> >Let M be the nondeterministic Turing machine (NTM) that decides HAMPATH. We
> >design an NTM N that decides coHAMPATH as follows:
> >
> >N=``On input <G,s,t>:
> >    1. Run M on input <G,s,t>
> >    2. If M accepts, reject. Otherwise, accept.''
> >
> >If M accepts on input <G,s,t>, then <G,s,t> is in HAMPATH, ie, <G,s,t> is not
> >in coHAMPATH. If M rejects on input <G,s,t>, then <G,s,t> is not in
> >HAMPATH, ie, <G,s,t> is in coHAMPATH. Since there is an NTM that decides
> >coHAMPATH, it follows that coHAMPATH is in NP.
> >
> >(qed)
> >
> >Is there something wrong with my "proof"
> >
> Indeed there is. A deterministic Turing machine accepts an input if and
> only if it does not reject it.
>
> However, when we introduce nondeterminism, this duality between
> acceptance and rejection is lost.
> A nondetermistic Turing machine accepts an input w if SOME computation
> on w halts in an accepting state, whereas it rejects an input w if ALL
> computations on w halt in a rejecting state.


> In your "proof" above, the machine M may choose a computation such that
> <G,s,t> is rejected even though there is another possible computation
> which would cause <G,s,t> to be accepted. Thus, we cannot conclude that
> if M rejects <G,s,t>, then there is no hamiltonian path from s to t in G.

However, we know that nondeterminism is biased towards acceptance as you
pointed out earlier. That is, M rejects an input w if ALL computations
on w halt in a rejecting state, and accept otherwise. Thus, if M
rejects on input w, there *can't* be a hamiltonian path from s to t in G
for otherwise some branch of computation on w will accept.

Anthony

Anthony WIDJAJA <twidjaja@students.cs.mu.OZ.AU> wrote:

( I wrote: )

> > In your "proof" above, the machine M may choose a computation such that
> > <G,s,t> is rejected even though there is another possible computation
> > which would cause <G,s,t> to be accepted. Thus, we cannot conclude that
> > if M rejects <G,s,t>, then there is no hamiltonian path from s to t in =
G.
>
> However, we know that nondeterminism is biased towards acceptance as you
> pointed out earlier. That is, M rejects an input w if ALL computations
> on w halt in a rejecting state, and accept otherwise. Thus, if M
> rejects on input w, there *can't* be a hamiltonian path from s to t in G
> for otherwise some branch of computation on w will accept.

What you write above is not correct. Let me try to restate my original
reply.

Given an input w, the NTM M gives rise to a tree of configurations whose
root is the inital configuration and whose branches all have length at
most f(|w|), where f is the worst-case time complexity of M.

M accepts w if SOME branch ends in an accepting configuration. There may
be several other branches of the computation tree which end in rejecting
configurations.

The archetypal M is the following:

        Given graph G =3D (V,E) and s,t in E

=091. Nondeterministically choose a finite sequence of edges S of
           length at most |V|.
        2. Check if S is a Hamiltonian path from s to t.
           If yes, then accept, else reject.

Clearly the above machine always terminates and accepts iff G has a
Hamiltonian path from s to t. It is also obvious that on most inputs it is
the case that some computations of M will lead to a reject state.

In general, when you run an NTM M with w as input ONCE and a rejecting
configuration ensues, then you do not know whether w is a member of L(M)
or not. To determine this, you must check if ALL branches end in a
rejecting configuration.  To perform this check, you need to explore the
entire computation tree of M with w to see if there it contains an
accepting branch. It is unlikely that this can be done in polynomial time.

Essentially, this boils down to a fundamental asymmetry between the
existential and universal quantifiers. To determine the truth of an
existential formula \exists x. P(x), you only need to find a witness a
such that P(a) holds. On the other hand, to determine the truth of a
universal formula \forall x. P(x), you must check that P(x) holds for any
choice of x.

Hans

--
Hans H=FCttel                        | email: hans@cs.auc.dk
BRICS, Dept. of Computer Science   | WWW: http://www.cs.auc.dk/~hans/
Aalborg University                 | tel.: (+45) 96 35 88 88
Fredrik Bajersvej 7E               | fax: (+45) 98 15 98 89
9220 Aalborg =D8, DENMARK            | Fight spam!  http://www.cauce.org

Hi,

Thanks for the reply. If I try proving that coHAMPATH is in NP by
coming up with a verifier for it, I have not yet succeeded. I know
that if coHAMPATH is really in NP, it follows that NP=coNP which
would be contradictory to what most of us believe. Therefore, I now
suspect there is something wrong with my arguments. However, I have some
worries with your arguments (see below)

> The archetypal M is the following:
>
>         Given graph G = (V,E) and s,t in E
>
> 	1. Nondeterministically choose a finite sequence of edges S of
>            length at most |V|.
>         2. Check if S is a Hamiltonian path from s to t.
>            If yes, then accept, else reject.
>
> In general, when you run an NTM M with w as input ONCE and a rejecting
> configuration ensues, then you do not know whether w is a member of L(M)
> or not. To determine this, you must check if ALL branches end in a
> rejecting configuration.  To perform this check, you need to explore the
> entire computation tree of M with w to see if there it contains an
> accepting branch. It is unlikely that this can be done in polynomial time.

The point you make regarding the number of times we need to run M on w
confuses me. You gave me an impression that M *randomly* chooses a
finite sequence of edges, instead of *nondeterministically*. By
definition, M *will* find an instance of hamiltonian path if there is
one. So, there is some kind of built-in function that can check if
some computation branches end up accepting (this can be done in one
function call). Using this as a subroutine, we can check it's negation
which is "there isn't any accepting computation branch on input w".
Moreover, M rejects if and only if <G,s,t> is not in HAMPATH for otherwise
M is not a decider for HAMPATH (anyway, this is equivalent to saying
M accepts if and only if <G,s,t> is in HAMPATH).

By the way, what is your definition of nondeterminism? Can you explain
your point on "the duality between acceptance and rejection is lost
when nondeterminism is introduced"? Since I don't think it is the case.
That is, if M accepts on input w, then there exists an accepting
configuration and thus not all configurations are rejecting and so
M does not reject. Conversely, if M does not accept w, then there doesn't
exist an accepting configuration and thus all configurations are rejecting
which means that M rejects w. This proves that an NTM N accepts w iff
N does not reject w.

Thanks in advance,

Anthony