Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science

learn more… | top users | synonyms

0
votes
1answer
19 views

Languages in coNP

if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it? i think that this is false, but am unsure how to show it? my guess is using ...
3
votes
0answers
44 views

NP-complete impossible to solve in $O(n)$

NP-complete problems are likely to be unsolvable in polynomial time (although no one proved it yet). My question is, has anybody proved that they are unsolvable in $O(n^d)$ for some concrete small ...
3
votes
2answers
45 views

Proving UNIT INTERSECTION NP-complete [duplicate]

I am working on some review problems right now and am extremely stuck on how to solve problem - any help would be so appreciated. We are told to consider the following combinatorial problem: Unit ...
-2
votes
0answers
21 views

How to reduce the Partition Problem to 3-Partition?

Given a set of natural numbers. Show the problem of following is NP-complete: decide if the set can be partitioned into three disjointed subsets that have equal sums and the union of them is the ...
0
votes
0answers
26 views

Simple Turing machine problems [duplicate]

I'm trying to go over some review problems regarding Turing Machine recognizability, and am still pretty confused about the following problems. This is the only information we are given in the problem ...
1
vote
1answer
104 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
2
votes
1answer
35 views

What is the “true” minimum spanning forest of a connected graph?

Normally, a minimum spanning forest of a graph G is defined as the union of minimum spanning trees of each of its components. This definition is a generalization of the minimum spanning tree of a ...
-2
votes
0answers
34 views

prove that Minesweeper game is Np complete [closed]

In the minesweeper game, there is a two-dimensional array of cells partially filled with hidden mines. You have to uncover all non-mined cells. These cells contain values between 0 and 8 indicating ...
1
vote
1answer
24 views

0/1 knapsack upper bound

I'm new to the 0/1 knapsack problem and I've ordered my nodes into profit/weight as: Knapsack max weight: 12 ...
1
vote
1answer
39 views

Given that Minimum Spanning Tree is NP-complete show that Hamiltonian Cycle is NP complete

So first of all I know finding MST is in P and is not NP complete. But I checked last year exams from my University and there is a problem: Given that Minimum Spanning Tree is NP-complete show that ...
1
vote
2answers
41 views

Is showing a graph is non-Hamiltonian NP-Complete?

Show that graph is not Hamiltonian. Is this an NP-complete problem? My guess is that this is not an NP-complete problem, because we can run DFS and check it. Like, if we have a Hamiltonian cycle ...
3
votes
2answers
83 views

An easy question about NP-hard

Consider an optimization problem includes two variables. If we fix the value of one variable, then the optimization problem over the other variable is NP-hard. Can it be concluded that the original ...
1
vote
0answers
19 views

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that

Given inputs as positive integers $a$,$b$, and $c(i,j)$ where $i,j\leq a$, decide if there is a permutation $\tau$ such that $$c(\tau(a),\tau(1))+\sum_{i=1}^{a-1} c(\tau(i),\tau(i+1))\leq b $$ Prove ...
0
votes
1answer
54 views

Need help to understand the solution for NP-completness proof (3CNF <= 0-1 integer-programming problem)

I was trying to solve problem from Cormen page 1100 34.5-2 Given an integer $m * n$ matrix A and an integer $m$-vector $b$, the 0-1 integer- programming problem asks whether there exists an integer ...
2
votes
1answer
31 views

If $P = NP \cap coNP$, can $P \ne NP$?

In Scott Aaronson's Quantum Computing since Democritus he writes on page 65: Indeed, for all we know, it could be the case that $P = NP \cap coNP$ but still $P \ne NP$. The same statement is in ...
0
votes
2answers
47 views

P vs NP and Countable vs Uncountable Decision Space

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision ...
1
vote
0answers
25 views

If a problem in $P$ can be rewritten to $NPC$, why can this $NPC$ problem not be solved in polynomial time?

According to multiple definitions and my math professor, problems in $NP$ can be rewritten to a problem in $NPC$, including problems in $P$. Why can I solve a $P$ problem in polynomial time, but can't ...
-1
votes
1answer
17 views

Question about NP with certificate

all. I have some question about proving NP-complete The conditions of proving problem is NP-complete is following. 1) Problem is in NP 2) Problem is reducible other from NP-Complete Problem (Ex. ...
1
vote
1answer
30 views

NP HARD Problem Longest Path in Graph

I got stuck with this problem since the whole day. When we are finding the longest path in a graph we first do topological sorting and then check the path of adjacent vertices and keep upgrading ...
2
votes
2answers
109 views

Is this an NP-Complete problem? (unweighted & undirected graph)

G is an unweighted, undirected graph. Then, I cannot prove that [deciding whether G has a path of length greater than k] is NP-Complete. How can I show whether the algorithm is NP-complete or not?
1
vote
1answer
64 views

A decision problem that is Cook reducible to its complement

I'm taking an algorithms course and we are covering polynomial time reductions, and I've read online that many decision problems are polynomial-time reducible to their complements. Can anyone give me ...
1
vote
1answer
43 views

What is a good example of an algorithm that is hard to parallelise?

When I have 10 computers, the factorization of a number doesn't scale along. I am not sure how much faster it would go compared to a single computer, but not 10 times faster like one would expect. ...
1
vote
1answer
14 views

Reducing a problem X to an np-complete problem Y.

Say I have a problem X that I can reduce to an NP-complete problem Y. Can I assume that problem X is in NP? Can it not be in NP?
2
votes
2answers
84 views

P vs NP - examples of P and NP

I'm currently studying 'p versus np'. Can someone help me in showing an example of a mathematical p problem and np problem? A clear worked example would be much appreciated. Many thanks in advance.
2
votes
0answers
26 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
0
votes
0answers
33 views

Clique of size $k$ or vertex with degree $\geq \log |V|$ is in $P$?

Prove that $L=\left\{ \left\langle G,k\right\rangle \mid G\mbox{ contains a vertex of degree at least }\log_{2}|V|\mbox{ or a clique of size }k\right\}$ is in $P$ ($G$ is undirected graph and $k$ is a ...
1
vote
1answer
42 views

Clarification over what NP means

I'm reading an informal definition of the decision class NP with a specific example being the standard knapsack problem and a decision variant of this problem. The example they are using is a ...
0
votes
0answers
42 views

Prove that the following Horn satisfiability problem is P-complete

Show that the following Horn satisfiability problem is P-complete: given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the Boolean satisfiability ...
0
votes
0answers
31 views

Proof the Restricted Case of CVP is P-complete

Show that the following Restricted Case of CVP is P-complete: Like CVP, except the input circuit satisfying the following conditions: All gates are placed int layers; the inputs of a gate come from ...
4
votes
1answer
66 views

Is this graph theory problem NP-Complete?

Back in college I was in an introductory Graph Theory (undergrad) class. For one assignment I was creating an algorithm to solve the following problem: Find an odd-length cycle in a directed ...
3
votes
2answers
61 views

NP-Complete and Poly Time Reduction Problems [closed]

I Took Some Priminlairity Learning Method on Complexity Theory. I get trouble with some definition. anyone could help me, Why the mentioned statement is True? if a Problem A can be reducible to ...
0
votes
2answers
44 views

Satisfying assignments, twice-3SAT NP complete

I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments. "TWICE-3SAT Input: ...
-2
votes
1answer
65 views

some Graph and NP Theory Problems [closed]

my instructor solve the following problem, that which of the following is into a NP Class? ...
0
votes
0answers
7 views

about concurrent open shop problem

I am working on finding bounded heuristics for a NP-hard problem. I was wondering whether there are well-known bounded solutions. The problem is formulated as follows. Given a set of $D^{(k)}(1\leq ...
1
vote
1answer
55 views

Asymptotic and 3-SAT problem in Algorithm Course

my TA says just one of the following is True, anyone could describe me some detail about following three lines? 1- if $f_i$ be a function of natural numbers to natural numbers and $f_i(n)=O(n)$ then ...
0
votes
1answer
115 views

Reduce Hamiltonian Path to CNF SAT

I'm trying to figure out how to reduce a 5 vertex graph to a Boolean equation that will answer if the graph contains a Hamiltonian path. For a Hamiltonian Path to be present in a graph: Each vertex ...
2
votes
0answers
50 views

A simple graph problem that seems NP complete

Consider an arbitrary undirected graph where each node $i$ has an arbitrary cost $c_i>0$ and each edge has a weight of 1. The objective is to select a set of edges so that the total weight of the ...
0
votes
0answers
29 views

How to prove the NP-Completeness or NP-Hardness of this MINLP problem?

I am working on an optimization problem, which is an MINLP (with binary integers). Is this MINLP an NP-Hard problem or NP-Complete problem. And how to prove the hardness or completeness? Here ...
0
votes
1answer
60 views

Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?

Not sure whether this question belongs here or mathoverflow. You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be inside ...
3
votes
1answer
47 views

Find an assignment of courses to days so that no student has more than one exam on the same day is NP-complete?

Given a list of $N$ courses, $M$ students, the list of courses each student is taking and an integer $K$ representing the duration of the exam phase, is there an exam schedule consisting of $K$ dates ...
1
vote
1answer
935 views

The traveling salesman problem is NP-complete Reduction

The traveling salesman problem is NP-complete. Proof: First, we have to prove that TSP belongs to NP. If we want to check a tour for credibility, we check that the tour contains each vertex once. Then ...
2
votes
1answer
51 views

What is a simple proof that something is np complete that does not use np completeness of something else?

What is a simple proof that something is NP complete that does not use NP completeness of something else? Every proof seems to reduce to something else being NP complete.
2
votes
2answers
168 views

Knapsack problem NP-complete

Show that the knapsack problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint:Use the exact ...
1
vote
1answer
39 views

Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$

Suppose you find a reduction from the $k$-vertex-cut problem to the hamiltonian-path problem. In particular, you find an algorithm $A$ that, given the graph $G$ and the number $k$, outputs a ...
2
votes
1answer
45 views

NP Solvable in Polynomial Time

I just took an exam and am a little curious about this question (it may not be verbatim, but the idea is clear): TRUE/FALSE: If an NP complete problem can be solved in polynomial time, then P = NP. ...
0
votes
1answer
24 views

A language $L$ is polynomially transformable to $L_0$

Could someone explain to me the following definition?? A language $L$ is polynomially transformable to $L_0$ if there is a deterministic polynomial-time-bounded Turing machine $M$ which will convert ...
0
votes
2answers
78 views

Proof NP-Complete for $L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$

$L = \{G, T \mid G \text{ is a graph with a spanning tree isomorphic to } T\}$ and I try to prove it's NP-Completeness. It seems really easy since obviously it is at least as hard as HAM-PATH which is ...
1
vote
1answer
42 views

Is a subset of a NP-complete language also NP-complete?

For example, we know that $SAT$ is NP-complete. However, what if we have a set $subSAT \subset SAT$. Is $subSAT$ NP-complete? What if we have a set $numSAT$ where $numSAT = \{ x \in SAT \; | \; |x| ...
0
votes
2answers
37 views

3-COLOR Decision Problem

The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color. The reduction from 3-SAT to 3-COLOR uses the ...
2
votes
2answers
113 views

Efficiency of a max-min problem for $\sum_{j=1}^m |b_j-a_j|$ with $a_i$, $b_j$ restricted to convex sets

Consider the following optimization problem: $$\max_{\{a=(a_1,a_2,\ldots,a_m)\in A\}}\min_{\{b:=(b_1,\ldots,b_m)\in B\}} \sum_{j=1}^m |b_j-a_j|.$$ Is computing the optimal value of this problem ...