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

learn more… | top users | synonyms

0
votes
2answers
28 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
21 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
15 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
20 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
51 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
0answers
56 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
42 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
13 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
78 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
22 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
32 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
39 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
35 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
26 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
62 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
52 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
34 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
59 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
52 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
100 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
47 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
28 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
39 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
378 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
50 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
147 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
38 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
32 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
39 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
37 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
33 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
88 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 ...
2
votes
1answer
59 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
27 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
19 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
54 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
46 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
123 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
48 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
36 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
76 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
37 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
35 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
24 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
66 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
86 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
26 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 ...