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

learn more… | top users | synonyms

2
votes
1answer
53 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
28 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
27 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
19 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
0answers
30 views

Show that it is NP-complete [closed]

Show that the problem of determining whether a regular expression over the alphabet $\{0\}$ does not denote $0^*$ is NP-complete. Could you give me some hints how I could do that??
0
votes
2answers
35 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
25 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
24 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
64 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 ...
1
vote
1answer
30 views

Reduction of 3-SAT to 3-COLOR

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color. I had ...
1
vote
1answer
23 views

Transportation mininum cost problem

I've got a bit stuck trying to solve the following problem: A number of transport companies each offer various means of transportation, for example company A offers: ...
0
votes
1answer
17 views

Complexity of Subset-Sum when the target sum is a constant

The Subset-Sum decision problem is: Given a set of n non-negative integers S, is there a subset of S that sum to k? If S and k are inputs, the problem is known to be NP-Complete. What about ...
0
votes
1answer
24 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
1answer
42 views

How do you load $n$ cannisters into $m$ trucks such that no truck is overloaded

We have $n$ cannisters, and for each one there is a specified subset of trucks which can carry it. There are $m$ trucks that can each hold $k$ cannisters. Is there a way to load all $n$ cannisters ...
4
votes
3answers
111 views

Using up letters on a refrigerator is NP-complete

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...
0
votes
1answer
32 views

Is knowing the size of a minimum vertex cover equivalent to finding a minimal cover?

As most of you know, the problem of finding a minimal vertex cover for an arbitrary graph is an NP-hard problem. I was wondering, if there existed a non-constructive way of calculating the size of a ...
0
votes
1answer
23 views

Proof of why the partition function Z in probabilistic graphical models (PGM) is NP-complete

I was wondering if someone knew why computing the partition function for probabilistic graphical models is NP-Hard? I would like to see a full blown rigorous proof, however, I am as happy to get a ...
0
votes
2answers
67 views

Is there a problem more difficult than NP-complete in graph theory?

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled ...
0
votes
0answers
22 views

Variation of Bin-packing with classes of bins and objects

I'm working on a problem that is a variation of bin-packing, but a bit more general form with extra constraints. The problem definition is as follows- We have objects of varying sizes, which can be ...
0
votes
2answers
31 views

P and NP and NP-complete and NP-hard in simple terms

I'm trying to wrap my head around what all these terms mean and here is my understanding so far. I'm hoping you can improve my understanding of what these terms mean. P is the set of all problems ...
0
votes
1answer
17 views

Non-Deterministic Polynomial Time Algorithm

My understanding is that for problems where there are an exponential number of possible solutions, a non-deterministic turing machine (NTM) is able to solve it in polynomial time because an NTM can ...
0
votes
2answers
63 views

Minimizing sum of products

Consider a total of $d$ items, $\{I_1, I_2, \cdots, I_d \}$, each having a weight $w_i$, and a total of $m$ bins, $\{B_1, B_2, \cdots, B_m\}$. We would like to distribute the items into the bins such ...
1
vote
1answer
57 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
0
votes
1answer
25 views

NP-Completeness and NP

Given : $S$ is an $NP-Complete$ problem $Q$ and $R$ are two other problems not known to be in $NP$. $Q$ is polynomial-time reducible to $S$ and $S$ is polynomial-time reducible to $R$. My thoughts ...
2
votes
1answer
71 views

Verifier and Certificate for coNP SUBSET-SUM

The original SUBSET-SUM problem is "given a set of integers, is there a non-empty subset whose sum is zero?" If we look at the inverse problem: "given a finite set of integers, does every non-empty ...
3
votes
3answers
142 views

Minimum vector sets span spaces cover problem

Instance: a set of vectors $V=\{\mathbf{v}_1,\mathbf{v}_2,...,\mathbf{v}_n\}$ and $m$ vector sets $V_1,V_2,...,V_m$, each of which contains multiple vectors ($V_i$ may not be a subset of $V$). In our ...
0
votes
0answers
16 views

Vertex Cover Approximation

Is there any Vertex Cover approximation algorithm that gives the optimal solution for some graphs but otherwise near-optimal solutions for other graphs? Would an algorithm like that be useful? From ...
1
vote
2answers
202 views

Proving Hamiltonian Cycle is NP Complete

I'm trying to learn Complexity classes.I want to show Hamiltonian cycle is NP Complete. The text tells me that Inorder to prove NP-Completeness we first show it belongs to NP,by taking a ...
15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
1
vote
1answer
88 views

Prove that the “even” subset sum problem is NP-complete

I need to prove that the even subset sum problem is NP-complete. "Given a finite set of natural numbers and an even number $n$, decide whether a subset of the given set exists such that the ...
2
votes
0answers
30 views

Decidability of $P = NP$?

(Please, don't sign this as duplicate of this question, they are not.) Is it possible, that the well-known $P=NP$ conjecture is undecidable in ZFC? Is there any result about this topic?
1
vote
1answer
23 views

Trying to prove something in complexity

I just started to learn about complexity-theory, and I'm trying to prove this: If P=NP, then every (non-trivial) language in P is NP-complete. Can someone give me a solution please?
1
vote
0answers
53 views

Math Symbols for “Must be Finite”

I want to express the following two sentences in mathematical syntax (if possible): The number of solutions to the problem should be finite and each solution should be of polynomial length More ...
3
votes
2answers
154 views

Proof that SAT is NPC

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem). I read the proof with all its parts corresponding to the Turing machine TM solving it (TM ...
1
vote
1answer
99 views

Mixed Q horn SAT

I am familiar with Horn formula: Formula whose clauses have atmost one positive literal. I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn. Question 1: But, ...
1
vote
1answer
54 views

Existence of a trail of given length in a graph - NPC?

I am trying to determine, whether the problem of a trail of given length in a graph is a NPC problem. We have a graph $G = (V, E)$ and $k \in N^+$. Does this graph contain a trail of length at least ...
0
votes
0answers
32 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
1
vote
1answer
28 views

Polynomial Reduction for restriction

I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true? $$ L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1 $$ Thanks!
1
vote
1answer
56 views

Relation of encryption to P, NP, and NP-Complete

After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
1answer
125 views

P, NP-Complete and NP-Hard Problems

I have confusion over P, NP-Complete and NP-Hard problems. I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
0
votes
1answer
29 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
0
votes
2answers
117 views

What does psuedo-polynomial algorithm for subset sum problem mean?

Help me out here - just trying to better understand what 'psuedo-polynomial' means... If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
2
votes
1answer
67 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
0
votes
3answers
72 views

Gaining Mid-level Understanding of P vs NP

I have a base understanding of N and NP, but I want to find some material to gain a better understanding to it. E.g. 'Mid-level', something that goes more into depth of it. Any suggestions for PhD ...
0
votes
1answer
143 views

Chaos Theory and Sum Subset Problem

In respect to the "P versus NP" controversy, can't chaos theory be used to solve problems like the Sum Subset Problem with non exponential performance? Like, chaotic equations, are like paths to very ...
6
votes
1answer
740 views

Why is Dantzig's solution to the knapsack problem only approximate

For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
0
votes
0answers
14 views

In the definition of NP, is it required to have polynomially bounded length of certificate?

So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
0
votes
1answer
53 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
0answers
52 views

What is an algebraic expression over a field structure?

I am working on a problem, and I am not understanding the language very well. Here is the setup of the problem: Consider the set $\{ 0, 1, 2 \}$ with the operations addition $(+)$ modulo $3$ and ...
1
vote
2answers
99 views

Which pure mathematical problems could be tackled with an algorithm solving NP-complete problems?

In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for ...