Assignment 6
CS-GY 6033 INET Fall 2024
Due date: Dec 16th 2024, 11:55pm
Question 1: Complexity classes
12 points
Short answers!
Consider the following problems. For each problem, determine if it is possible that there exists a polynomial-time algorithm for solving that problem. Justify your answer using what is currently know about their complexity classes.
● Travelling salesman problem
● n × n chess
● The Halting Problem
● Vertex Cover
● Integer Factorization
● Given a set of n items, where each item has a specific weight, can we pack them onto K trucks where each truck can hold at most weight B .
Question 2
12 points
Below are a list of runtimes for decision problems. For each runtime, determine if the corresponding problem is in P or EXP or both or neither.
1. T(n) = (log n)6
2. T(n) = log(n6 )
3. T(n) = (6n)6
4. T(n) = n + 1000
5. T(n) = nn
6. T(n) = 3n + n6
7. T(n) = 3n2 +6
Question 3
27 points
For each problem below, determine whether or not there is a known polynomial-time algorithm for solving the problem. You must justify why there is no known poly-time algorithm OR identify a poly-time procedure that solves the problem.
(a) Consider a the political meeting which has n participants. There are m issues which are to be discussed at the meeting. Each participant must list exactly two issues that interest them. The organisers would like select at most k issues, so that each person is interested in at least one of the selected issues.
(b) A graph G has n vertices and m edges. The problem is to determine if G contains a simple cycle of length at least 3.
(c) A graph G has n vertices and m edges. The problem is to determine if G contains a simple cycle of length at least k
(d) A directed graph G contains n vertices and m edges. The problem is to determine if there is path from vertex s to every other vertex in the graph.
(e) A directed graph G contains n vertices and m edges. The problem is to determine if there is path from vertex s to and from every other vertex in the graph.
(f) A directed graph G contains n vertices and m edges. The graph is not weighted. The problem is to determine if there is path from vertex s to every other vertex in the graph, where the number of edges in the path must be at most k.
(g) A directed graph contains n vertices and m edges. The problem is to determine if G is a DAG.
(h) An undirected graph has weighted edges. The problem is determine if there is a path that starts at vertex s and travels to vertex t where the sum of the edge weights is less than k.
(j) An undirected graph has weighted edges. The problem is determine if there is a path that starts at vertex s and visits all vertices exactly once, where the sum he edge weights is less than k.
Question 4
10 points
Prove that the following problem is NP-complete using a reduction from either : Vertex Cover, Inde- pendent Set, Dominating Set, or Clique. Recall the two steps that are necessary in order to show that a problem is NP complete.
A set of n people attend a political meeting, where m issues are to be discussed. Each person attending has created a sublist of issues (selected from the main set of m issues) that they are most interested in. The organisers would like to select at most k issues so that each person is interested in at least one of the selected issues. The problem is to determine if it possible or not.
Question 5
10 points
Prove that the following problem is NP-complete using a reduction from either: Vertex Cover, In- depednent Set, Dominating Set, Subset Sum, Hamiltonian cycle, or Clique. Recall the two steps that are necessary in order to show that a problem is NP complete.
A graph G consists of a set of n vertices and m edges. A specific vertex is labelled S. The problem is to determine if there is a simple path that starts at vertex S and visits all other vertices in the graph.