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

learn more… | top users | synonyms

10
votes
1answer
51 views

Arranging a set of strings to form a palindrome: NP complete?

Is it NP complete to determine if a given set of strings can be arranged to form a palindrome? Example: The strings {"German" "man" "am" "am" "I" "I" "regal" "a"} can be arranged into "I man am regal ...
2
votes
1answer
26 views

Can CNF Hamiltonian graphs be turned to “DNF” graphs?

Given a CNF SAT formula, we can turn it into a Hamiltonian graph, which is Hamiltonian iff the formula is satisfiable. Now, we can transform the CNF formula into a DNF one. My question is, can the ...
2
votes
1answer
32 views

Are there any “proof schemes” for P $\neq$ NP?

Let me contextualize the title to make myself clearer: thanks to Cook–Levin theorem, there is a well known, and easy to understand way to prove that $P = NP$. It is known that if one can prove that an ...
0
votes
1answer
36 views

Coin Change Problem with Fixed Coins

Problem: Given $n$ coin denominations, with $c_1<c_2<c_3<\cdots<c_{n}$ being positive integer numbers, and a number $X$, we want to know whether the number $X$ can be changed by $N$ coins. ...
0
votes
1answer
29 views

NP-complete proof of subset with sum zero

I'm trying to proof that a problem of subset from a group has a sum of zero. I know that i can use the partition problem that is known to be NP-complete, but i can't seems to find what i need to ...
1
vote
0answers
14 views

Minimum vertex cover of vertex disjoint odd holes and antiholes

I am interested in knowing whether the minimum vertex cover of a graph that can be written as the union of vertex-disjoint odd holes and odd antiholes can be found exactly, in polynomial time. I could ...
2
votes
0answers
13 views

Is cubic graph decomposition into claws NP-complete?

I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
-4
votes
1answer
56 views

Why is it that if one NP complete problem is solved, all NP problems are solved?

I get NP completeness, but I don't understand why it's said that by solving one NP complete problem, all of them are solved. Is it saying that solving one NP complete problem proves that all of them ...
0
votes
1answer
42 views

Prove $K_4-Cover$ is NP-Complete

I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams. I have come across this problem and I'm having some difficulty with it: Let $ G ...
1
vote
0answers
13 views

2HP - Edge Disjoint Hamilton Paths

G is a directed graph and s and t are 2 vertices in G. $2HC = \{(G, s, t): \; G $ has at least 2 edge-disjoint Hamilton paths $\}$ Prove that $2HC$ is NP-Complete. I'm trying to reduce UHAMPATH to ...
1
vote
0answers
25 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
1
vote
1answer
53 views

Optimize for happiness and equality

I'm trying to solve an optimization problem: There are $N$ students who can choose to enroll into $C$ courses, each of them has a set of 3 preferences $P = \{c_1, c_2, c_3\}$ about the courses they ...
12
votes
3answers
733 views

Must an algorithm that decides a problem in NP also produce a solution?

I think I have a basic misunderstanding in the definition of a decision problem. It's widely believed that a proof of P=NP would break all modern cryptography, for example:- ...
0
votes
0answers
53 views

Why finding chromatic number is NP-Hard?

We know that the chromatic number of a graph $G$ is the smallest number of colors needed to color the vertices of $G$ so that no two adjacent vertices share the same color . But why the coloring is ...
2
votes
1answer
32 views

Is it known whether a hypothetical P-time NP-complete decision procedure has to find a specific solution to the given constraint satisfaction problem?

Suppose a hypothetical decision procedure $A$ could solve NP-complete problems in polynomial time (of course implying $NP = P$). Many NP-complete problems take the form of constraint satisfaction, ...
2
votes
1answer
88 views

Why doesn't the decision problem for Presburger arithmetic demonstrate that $\mathsf{P} \neq \mathsf{NP}$

From Wikipedia's article on Presburger arithmetic: Then Fischer and Rabin (1974) proved that any decision algorithm for Presburger arithmetic has a worst-case runtime of at least $2^{2^{cn}}$, ...
2
votes
1answer
29 views

Are there slight modifications to NP-complete problems which reduce them to P?

Recently I revisited the infinite harmonic series and its barely diverging sum, and how removing all the composite numbers from the sum still produces a divergent series (even more barely). In ...
0
votes
0answers
36 views

Why aren't all NP-complete problems strongly NP-complete, if any NP problem can be reduced to an NP-complete problem

So we know that : (1). A problem is NP-complete if every other problem in NP can be reduced to it in polynomial time (2). A problem is said to be strongly NP-complete if a strongly NP-complete problem ...
0
votes
0answers
39 views

Proving NP-completeness

I want to prove the following problem is NP-Complete: $$\text{Given a weighted graph } G=(V,E), \text{ a vertex } v\in V \text{ and a number } K $$ The answer is YES if there exist a path of weight ...
0
votes
1answer
12 views

max degree polynomial for time complexity considerations

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some ...
0
votes
0answers
22 views

(Proving NP Hardness) Maximizing ratio of polynomials

I have a function $\prod_{i = 1}^N \alpha_i$ $\alpha_i = \displaystyle \frac{(\sum_{j = 1}^{M} R_j x_j I_i(j))^2}{\sum_{j = 1}^{M} R_j x_j}$ The variables are $x_j$s, and $R_j$s are some positive ...
2
votes
1answer
32 views

Is $P^{SAT}$ equal to NP $\cup$ co-NP?

I have following problem: Is $P$ with a $SAT$ oracle equal to $NP \cup coNP$ assuming that $NP \neq co-NP \neq P $? I can show that $NP \subseteq P^{SAT}$ and $coNP \subseteq P^{SAT}$. But it is much ...
0
votes
1answer
19 views

Is bipartite maximal matching an NP Hard or NP Complete or neither?

Is the bipartite maximal matching problem is NP hard or NP complete or neither? If it's either can someone cite a paper saying so? Also, if its not too trivial to ask, can someone explain NP Hard and ...
3
votes
1answer
74 views

CLIQUE to UNARY-CLIQUE reduction NP complete

Assume the following Language: UNARY-CLIQUE= $\{(G=(V,E),1^k) \mid G$ is an undirected graph and there is a clique of size $k$ in $G\}$ I'm trying to determine whether this language belongs to NP ...
0
votes
1answer
20 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
55 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
48 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 ...
0
votes
0answers
28 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
109 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
58 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 ...
1
vote
1answer
47 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
57 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
47 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
90 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
20 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
64 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
35 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
64 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
31 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
18 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
38 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
127 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
70 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
48 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
17 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
100 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
30 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
40 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
45 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
52 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 ...