Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 8: Q17E (page 281)

Show that for any problem ∏ in NP, there is an algorithm which solves n in time O 2pnwhere is the size of the input instance and p(n)is a polynomial (which may depend on∏ ).

Short Answer

Expert verified

The running time of the algorithm is as follows: pn=∑pnO2pn

Step by step solution

01

Introduction to the problem

An algorithm that solves the given problem in time O2pnis as follows:

For every string that belongs to∑nand accepted by the certifier, there is a polynomial time and a certificate that belongs to ∑n.

The time is Cs,t≤pn.

Generate all the possible strings tand test whether Cs,tis true underpn steps.

02

Prove that there exist an algorithm to solve given problem

The set of strings is represented by ∏.

Over an alphabet which is finite ∑n nature, the string is called as the instance.

An algorithm decides a problem to be yes if belongs to∏ .

The algorithm will execute for polynomial time if for every string , the algorithm on will terminate with at-most pstrsteps.

The represents the polynomial time.

The running time of the algorithm is as follows:pn=∑pnO2pn

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

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

In task scheduling, it is common to use a graph representation with a node for each task and a directed edge from task i to j task if i is a precondition for j. This directed graph depicts the precedence constraints in the scheduling problem. Clearly, a schedule is possibe if and only if the graph is acyclic; if it isn’t, we’d like to identify the smallest number of constraints that must be dropped so as to make it acyclic.

Given a directed graph G=(V,E), a subset E'⊆Eis called a feedback arc set if the removal of edges E' renders G acyclic.

FEEDBACK ARC SET (FAS): Given a directed graph G=(V,E)and a budget , find a feedback arc set of role="math" localid="1658907144825" ≤bedges, if one exists.

(a)Show that FAS is in NP.

FAS can be shown to be NP-complete by a reduction from VERTEX COVER. Given an instance (G,b)of VERTEX COVER, where G is an undirected graph and we want a vertex cover of size ≤b, we construct a instance (G',b)of FAS as follows. If G=(V,E)has vertices v1,K,vnthen make G'=(V',E')a directed graph with 2n verticesw1,w1',k,wn,wn',andn+2|E|(directed) edges:

  • (wi,wi')foralli=1,2,k,n
  • (wi',wj)and(wj',wi)forevery(vi,vj)∈E.
  • Show that if G contains a vertex cover of size b, then G' contains a feedback arc set of size b .
  • Show that if G' contains a feedback arc set of size b, then G contains a vertex cover of size (at most) b. (Hint: Given a feedback arc set of size b in G', you may need to first modify it slightly to obtain another one which is of a more convenient form, but is of the same size or smaller. Then, argue that G must contain a vertex cover of the same size as the modified feedback arc set.)

STINGY SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer K , find a satisfying assignment in which at most K variables are true, if such an assignment exists. Prove that isNP -complete.

In the NODE-DISJOINT PATHS problem, the input is an undirected graph in which some vertices have been specially marked: a certain number of “sources” s1,s2,…,sk and an equal number of “destinations” t1,t2,…,tk. The goal is to find k node-disjoint paths (that is, paths which have no nodes in common) where the ith path goes from si to ti. Show that this problem is NP-complete.Here is a sequence of progressively stronger hints.

  1. Reduce from 3SAT .
  2. For a 3SAT formula with m clauses and n variables, use k=m+n sources and destinations. Introduce one source/destination pair (sx,tx)for each variable x , and one source/destination pair (sc,tc) for each clause c .
  3. For each 3SAT clause, introducenew intermediate vertices, one for each literal occurring in that clause and one for its complement.

Notice that if the path from sc to tc goes through some intermediate vertex representing, say, an occurrence of variable x, then no other path can go through that vertex. What vertex would you like the other path to be forced to go through instead?

Give a simple reduction from 3D MATCHING to SAT, and another from RUDRATA CYCLE to SAT.

(Hint: In the latter case you may use variables xijwhose intuitive meaning is “vertex i is the j th vertex of the Hamilton cycle”; you then need to write clauses that express the constraints of the problem.)

Proving NP-completeness by generalization. For each of the problems below, prove that it is NP-complete by showing that it is a generalization of some NP-complete problem we have seen in this chapter.

  1. SUBGRAPH ISOMORPHISM: Given as input two undirected graphsG and H, determine whetherG is a subgraph of H (that is, whether by deleting certain vertices and edges ofH we obtain a graph that is, up to renaming of vertices, identical toG ), and if so, return the corresponding mapping ofV(G) intoV(H) .
  2. LONGEST PATH: Given a graph role="math" localid="1658141805147" Gand an integerg find inG a simple path of lengthg .
  3. MAX SAT: Given a CNF formula and an integer g, find a truth assignment that satisfies at least gclauses.
  4. DENSE SUBGRAPH: Given a graph and two integersa and b, find a set of a vertices ofG such that there are at leastb edges between them.
  5. SPARSE SUBGRAPH: Given a graph and two integersa andb , find a set of a vertices ofG such that there are at most bedges between them.
  6. SET COVER. (This problem generalizes two knownNP-complete problems.)
  7. RELIABLE NETWORK: We are given twon×n matrices, a distance matrixdij and a connectivity requirement matrixrij , as well as a budgetb ; we must find a graph G=({1,2,.....,n},E)such that (1) the total cost of all edges isb or less and (2) between any two distinct verticesi andj there arerij vertex-disjoint paths.
See all solutions

Recommended explanations on Computer Science Textbooks

Algorithms in Computer Science

Read Explanation

Theory of Computation

Read Explanation

Big Data

Read Explanation

Computer Organisation and Architecture

Read Explanation

Issues in Computer Science

Read Explanation

Data Representation in Computer Science

Read Explanation
View all explanations

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