Open In App

Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Introduction to Theory of Computation

Michael Sipser

Computer Science

3rd Edition · 458 pages

ISBN: 9781133187790

Chapter 0: Q20P (page 1)

We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ≠ NP

Short Answer

Expert verified

If PATH is not NP -complete, then $N P \neq P $ .$

Step by step solution

To assume PATH would ne NP-complete

EveryAisNPis polynomial time reducible toB.

G is a directed graph that has a directed path.

PATH is not NP - complete:

Let us assume that PATH would be NP - complete.

From the definition of NP - completeness,

To explain it’s true or not

Thus $P = N P$ which we believe that it is not true.

Hence, PATH is not NP - complete.

Assume that $P = N P$ and then show that PATH is NP - complete.

So assume $P = N P$ .

So, PATH is NP - complete.

Thus, if PATH is not NP -complete, then $P \neq N P$

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Myhill–Nerode theorem. Refer to Problem $1.51$ . Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the index of L to be the maximum number of elements in any set that is pair wise distinguishable by L . The index of L may be finite or infinite.

a. Show that if L is recognized by a DFA with k states, L has index at most k.

b. Show that if the index of L is a finite number K , it is recognized by a DFA with k states.

c. Conclude that L is regular iff it has finite index. Moreover, its index is the size of the smallest DFA recognizing it.

If we disallow $ε -$ in CFGs, we can simplify the $D K$ -test. In the simplified test, we only need to check that each of $D K$ ’s accept states has a single rule. Prove that a CFG without $ε -$ passes the simplified $D K$ -testiff it is a DCFG.

Recall, in our discussion of the Church–Turing thesis, that we introduced the language is a polynomial in several variables having an integral root}. We stated, but didn’t prove, thatis undecidable. In this problem, you are to prove a different property of—namely, that $D$ is -hard. A problem is -hard if all problems in are polynomial time reducible to it, even though it may not be in $N P$ itself. So you must show that all problems in $N P$ are polynomial time reducible to $D$ .

Let $A M B I G_{C F G} = \{< G > | G i s a n a m b i g u o u s C F G\}$ . Show that AMBIG_CFG is undecidable. (Hint: Use a reduction from PCP. Given an instance

$P = \{[\frac{t_{1}}{b_{1}}], [\frac{t_{2}}{b_{2}}], \dots, [\frac{t_{k}}{b_{k}}]\}$

of the Post Correspondence Problem, construct a CFG Gwith the rules

$S \to T | B$

$T \to t_{1} T_{a_{1}} | . . . . . | t_{k} T_{a_{k}} | t_{1} a_{1} | . . . . | t_{k} a_{k}$

$B \to b_{1} B | . . . | b_{1} B_{a_{k}} | . . . | b_{k} a_{k}$

where a₁,...,a_k are new terminal symbols. Prove that this reduction works.)

Show that the stringthe girl touches the boy with the flowerhas two different leftmost derivations in grammar $G_{2}$ on page 103. Describe in English the two different meanings of this sentence.

See all solutions

Recommended explanations on Computer Science Textbooks

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free

We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ≠ NP

Short Answer

Step by step solution

To assume PATH would ne NP-complete

To explain it’s true or not

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Computer Science Textbooks

Computer Organisation and Architecture

Computer Network

Databases

Cybersecurity in Computer Science

Computer Systems

Big Data

Study anywhere. Anytime. Across all devices.

Company

Product

Help