Let an arbitrary decision problem D, be: Given an instance I of the problem, is A true for I? The complementary decision problem, D', is then: Given I is A false for I? Show that if Dis a member...

1. 
   

   
   Let an arbitrary decision problem
   
   D,
   
   be: Given an instance
   
   I
   
   of the
   

   
   

problem, is

A

true for

I?

The

complementary

decision problem,

D',



is then: Given

I

is

A

false for

I?

Show that if Dis a member of

P

then so is

D'.

In contrast show that if

D

is a member of

NP

then we cannot necessarily draw the conclusion that

D



⁰



e




NP.

(If

D



e

P



then a

DTM





exists for

D



which halts within polynomial time for all

I.






D'





can then be solved by the same

DTM





by simply inter­ changing the states

q,



and

q


a.



On the other hand consider the case where

D



⁰










is the problem: Is it true that

there




does




not




exist



a travelling salesman's tour of length oi;.

k?


)