f



"Proof" that the complement of HAMPATH is in NP

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
0
twidjaja (3)
7/7/2003 8:54:38 AM
comp.theory 5139 articles. 1 followers. marty.musatov (1143) is leader. Post Follow

5 Replies
579 Views

Similar Articles

[PageSpeed] 16

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


0
hans6616 (16)
7/7/2003 9:07:17 AM
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/

0
gwoegi1 (15)
7/7/2003 9:10:41 AM
> >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
0
twidjaja (3)
7/7/2003 9:40:16 AM
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


0
hans6616 (16)
7/7/2003 12:26:45 PM
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
0
twidjaja (3)
7/7/2003 4:07:50 PM
Reply:

Similar Artilces:

""""""""""""""""""""""ADD ME""""""""""""""""""""
Hi , Hope you are doing great. Please let me take this opportunity to introduce myself, Iam Karthik working with BhanInfo Inc, a NY based company. We have consultants on our bench on various technologies, my request is to add me to your distribution list and kindly do send me the requirements. i have the below list available 1. Mainframe 2. Java 3.. Financial Analyst 4. Data Architect If there is any vendor ship agreement which has to be signed then I would like to take an opportunity to represent my company and expect your cooperation... We look forward to build a ve...

"""""""""ADD ME""""""""""
Hi , Hope you are doing great. Please let me take this opportunity to introduce myself, Iam Karthik working with BhanInfoi Inc, a NY based company. We have consultants on our bench on various technologies, my request is to add me to your distribution list and kindly do send me the requirements. i have the below list available 1. Mainframe 2. Java 3.. Financial Analyst 4. Data Architect If there is any vendor ship agreement which has to be signed then I would like to take an opportunity to represent my company and expect your cooperation... ...

Urgent Requirement in """""""""""""NEW YORK""""""""""""""""
Hello Partners, Please find the requirement below. Please send the updated resume along with rate and contact no. REQ#1: Title : Java Developer ( Rating Project) Duration : 6 months Rate : open Location : NY strong java, WebLogic 9.2, Web Services, Oracle REQ#2: Title : Java Developer Duration : 4 months Rate : open Location : NY Strong java, SQL REQ#3: Title : VB.Net Consultant Location : NY Duration : 4 months Rate : open Primarily looking at someone who has Excel, VB.net a...

"out" and "in out"
Hi i found the following explaination: In Ada, "in" parameters are similar to C++ const parameters. They are effectively read-only within the scope of the called subprogram. Ada "in out" parameters have a reliable initial value (that passed in from the calling subprogram) and may be modified within the scope of the called procedure. Ada "out" parameters have no reliable initial value, but are expected to be assigned a value within the called procedure. What does "have no reliable initial value" mean when considering the "out" parameter? By c...

about "++" and "--"
why this program snippet display "8,7,7,8,-7,-8" the program is: main() { int i=8; printf("%d\n%d\n%d\n%d\n%d\n%d\n",++i,--i,i++,i--,-i++,-i--); } > why this program snippet display "8,7,7,8,-7,-8" Ask your compiler-vendor because this result is IMHO implementation-defined. Check this out: http://www.parashift.com/c++-faq-lite/misc-technical-issues.html#faq-39.15 http://www.parashift.com/c++-faq-lite/misc-technical-issues.html#faq-39.16 Regards, Irina Marudina fxc123@gmail.com wrote: > why this program snippet display "8,7,7,8,-7,-8&q...

"my" and "our"
Hi, while testing a program, I erroneously declared the same variable twice within a block, the first time with "my", the second time with "our": { my $fz = 'VTX_Link'; .... ( around 200 lines of code, all in the same block) our $fz = 'VTX_Linkset'; ... } So the initial contents of the $fz declared with "my" is lost, because "our" creates a lexical alias for the global $fz, thus overwriting the previous "my" declaration. It was my error, no question. But I wonder why Perl doesn't mention this - even with "use s...

"If then; if then;" and "If then; if;"
I have a raw data set which is a hierarchical file: H 321 s. main st P Mary E 21 F P william m 23 M P Susan K 3 F H 324 S. Main St I use the folowing code to read the data to creat one observation per detail(P) record including hearder record(H): data test; infile 'C:\Documents and Settings\retain.txt'; retain Address; input type $1. @; if type='H' then input @3 Address $12.; if type='P' then input @3 Name $10. @13 Age 3. @16 Gender $1.; run; but the output is not what I want: 1 321 s. main H 2 321 s. main P Mary E 21 F 3 321 s...

why "::", not "."
Why does the method of modules use a dot, and the constants a double colon? e.g. Math::PI and Math.cos -- Posted via http://www.ruby-forum.com/. On Oct 26, 2010, at 01:48 , Oleg Igor wrote: > Why does the method of modules use a dot, and the constants a double > colon? > e.g. > Math::PI and Math.cos For the same reason why inner-classes/modules use double colon, because = they're constants and that's how you look up via constant namespace. Math::PI and ActiveRecord::Base are the same type of lookup... it is = just that Base is a module and PI is a float....

"or" and "and"
Hi, I'm just getting to discover ruby, but I find it very nice programming language. I just still don't understand how the "or" and "and" in ruby... I was playing with ruby and for example made a def to print Stem and Leaf plot (for those who didn't have a statistics course or slept on it, e.g. http://cnx.org/content/m10157/latest/) Here is the Beta version of it: class Array def n ; self.size ; end def stem_and_leaf(st = 1) # if st != (2 or 5 or 10) then ; st = 1 ; end k = Hash.new(0) self.each {|x| k[x.to_f] += 1 } k = k.sort{|a, b| a[0].to_f <=&g...

"/a" is not "/a" ?
Hi everybody, while testing a module today I stumbled on something that I can work around but I don't quite understand. >>> a = "a" >>> b = "a" >>> a == b True >>> a is b True >>> c = "/a" >>> d = "/a" >>> c == d True # all good so far >>> c is d False # eeeeek! Why c and d point to two different objects with an identical string content rather than the same object? Manu Emanuele D'Arrigo wrote: >>>> c = "/a" >>>&...

The term "theory" as in "database theory"
I have been working on a question related to the term "theory" and decided I first should get a better idea of what this term means to others. Below is the dictionary.com list of definitions. Which of the following comes closest to the use of the term "theory" in this ng as in "database theory", or is there another someone wants to provide? Thanks in advance. --dawn >From dictionary.com "1. a coherent group of general propositions used as principles of explanation for a class of phenomena: Einstein's theory of relativity. 2. a proposed ...

Urgent Requirement for """""""""""""""INFORMATICA DEVELOPER"""""""""""""
Hello Partners, How are you ? Please find the requirements below. Title: Database/ETL Developer Duration: 6 months Location: NY Exp: 7+ Locals preferred Database/ETL requirements (Mandatory) Candidate must have worked with financial instruments, preferably Mutual Funds but, Equities are also ok. PL/SQL - packages, Stored procs, Functions, Aggregate functions, Pipelined Functions Informatica 8.6 - especially complex mappings, complex maplets, complex workflows, transformations Oracle 10g/11g Unix/Linux shell scripting ...

Urgent need """""""""""INFORMATICA DEVELOPER"""""""""""""
Hello Partners, How are you ? Please find the requirements below. Title: Database/ETL Developer Duration: 6 months Location: NY Exp: 7+ Locals preferred Database/ETL requirements (Mandatory) Candidate must have worked with financial instruments, preferably Mutual Funds but, Equities are also ok. PL/SQL - packages, Stored procs, Functions, Aggregate functions, Pipelined Functions Informatica 8.6 - especially complex mappings, complex maplets, complex workflows, transformations Oracle 10g/11g Unix/Linux shell scripting Database/ETL requirements (Optional) ...

Does it need a ";" at the very after of "if" and "for"
write code like: int main(void) { int a=10; if(a<20) {} } Compiler ok on dev-cpp . don't we have to add a ";" after if statement? marsarden said: > write code like: > > int main(void) > { > int a=10; > if(a<20) > {} > } > > Compiler ok on dev-cpp . don't we have to add a ";" after if > statement? The syntax for 'if' is: if(expression) statement There is no semicolon after the ) but before the statement. The statement is either a normal statement (which can be empty), ending in a semicolon:- if(expr) ...

Web resources about - "Proof" that the complement of HAMPATH is in NP - comp.theory

Resources last updated: 2/8/2016 5:40:50 AM