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

learn more… | top users | synonyms

0
votes
0answers
17 views

What is an example of a search problem that is not in NP?

I feel like there should be an easy example, but I can't think of one. So, specifically, I am looking for a Yes/No search problem that is not in the class NP. When you learn about P and NP, you get a ...
1
vote
1answer
16 views

How exactly does a Max 2 Sat reduce to a 3 Sat?

Note: I've also asked this question on StackOverflow here I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard. However, if ...
2
votes
1answer
58 views

Problems in NP but not in NPc

Are there currently any known problems that are in NP but are known not to be NP complete?
-2
votes
1answer
43 views

Is there any significant consequence if P does not equal NP-complete?

I hear a lot on these forums about how if P=NP-complete how our lives would be better, is there any significant consequence if we found P to be not equal to NP-Complete?
4
votes
1answer
73 views

Formula for all possible sums of a binary sequence

Suppose I have a sequence, where for each element I can choose one out of two numbers. I would like to find a compact formula to write all the possible sums of all the possible sequences. For ...
2
votes
1answer
23 views

A query about reducting SAT to 3SAT when there are more than 3 literals in a clause

$C=a∨b∨c∨d∨e$ is a clause in SAT $D= (a∨b∨x)∧ (¯x∨c∨y)∧ (¯y∨d∨e)$ is the another form of C to make sure every clause has only threeliterals Is D true when C is true and false when C is false? Why? ...
1
vote
1answer
25 views

Scheduling problem on bipartite graph

Consider a bipartite graph $(G, U, V)$. Each $v$ in $V$ represents a soccer team, and each $u$ in $U$ represents a mini-tournament needs to be scheduled. If $u_i$ and $u_j$ share no common neighbor, ...
0
votes
0answers
22 views

SAT and NAE-SAT

Describe a polynomial-time transformation TRAN that takes an instance of SAT and transforms it into an instance of NAE-SAT (the problem where, given a Boolean expression in CNF form, you are asked, ...
0
votes
0answers
8 views

NP-Complete: reduce “L” the language such as circuits C1 and C2 compute the same function

I'm trying to reduce the NP-Complete language "CIRCUIT-SAT" (C is a boolean circuit that is satisfiable) to my language L, but my classmates are pointing out that i'm actually doing the opposite, ...
1
vote
0answers
88 views

Explaining Method of Pessimistic Estimators to Students

I need an alternative example for the Method of Pessimistic Estimators I need to give a lecture about the method of pessimistic estimators to computer science students. My lecture must be based on ...
1
vote
1answer
28 views

How do we decide a problem is in NP, but not in P or NPC?

As I understand, NPC set contains only the problems which can be polynomially converted into each other and which are hardest in NP set/ But how do we decide which problems are in NPC and which ...
2
votes
2answers
93 views

Can any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time? [closed]

Is it true to say that any NP-Complete problem can be reduced to any other NP-Complete problem in polynomial time?
0
votes
0answers
12 views

Np-hardness of a problem related to the knapsack problem

I am trying to know whether the following problem is NP-hard: Input: A positive number k and N pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$. The problem is to ...
3
votes
2answers
50 views

Why is triangle $\in P$ (P/NP)

I'm learning about $P/NP$ and my friend used an example in which he said that if you have a triangle in an undirected graph which is basically a set of three nodes in which all pairs of nodes are ...
0
votes
1answer
19 views

What the proof, instance, and verifier mean in the definition of NP problem?

I came across a definition of NP problems: Definition. A decision problem $X ∈ NP$, if there exists a polynomial time verifier $V$ such that For every yes instance $x ∈ X$, there exists a ...
0
votes
1answer
43 views

Traveling Salesman with exceptions

Assume a regular TSP problem with n cities. However, in this particular problem, we do not have to visit all the n cities, only a specific subset of them, m, where m<=n. The cities in n but not in ...
0
votes
1answer
34 views

Is it necessary for hamiltonian cycle to cover all the vertices of the graph??

I have read the definition on wikipedia and it says: In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each ...
0
votes
0answers
11 views

Minimum(maximum) cost of a weighted uni-height tree

If we have a rooted tree with all trunks the same height, and every vertex assigned a weight, is there a simple method to find the route from root to a leaf with minimum(maximum) cost?
0
votes
0answers
42 views

How to prove that problem is NP-hard by making a reduction?

Convering by triples Data: A set Y of cardinality 3n and a family C = ($C_{1},...C_{m}$) of triples of elements of Y: for all i, $C_{i}$ $\subset Y$ and |$C_{i}$| = 3. We admit that COVERING BY ...
-1
votes
1answer
44 views

How to prove the problem is in NP?

We have: Convering by triples Data: A set Y of cardinality 3n and a family C = ($C_{1},...C_{m}$) of triples of elements of Y: for all i, $C_{i}$ $\subset Y$ and |$C_{i}$| = 3. Problem: Is there a ...
0
votes
0answers
39 views

Proof of NP-completeness in the strong sense

I am just learning about the $\textbf{NP}$-completeness in the strong sense. I know that the $3$-partition problem: A set $X$ of $3n$ positive integers and a positive integer $B$ is given where each ...
0
votes
1answer
69 views

Is $P=NP$ an $NP$-complete problem?

Is $P=NP$ an $NP$-complete problem? In other words, is it possible (and does it make any sense) to show that proving $P=NP$ (or $P\neq NP$) cannot be done in polynomial time? I am not even sure it ...
0
votes
1answer
23 views

Why is there, for every language L in NP, a Turing machine with polynomial memory that also accepts L?

So my question is the title, but I also have a question about something else. If you have a problem, how can you determine the reason that it is in NP. So for example: given a directed graph with $N$ ...
1
vote
0answers
17 views

Is this projection optimization problem NP-hard?

Suppose we are working in ${\mathbb R}^d$ (dimension is not fixed), and we have a set of $n$ points $X = \{x_1,\ldots,x_n\}$ in that space. Given a query point $y$ inside the convex hull of $X$, we ...
4
votes
1answer
58 views

If P = NP, would that mean P=NP-Complete?

I just started learning about P vs Np and have a basic understanding of P, NP, and NP complete. I just wanted a little clarification on how each interacts with the others. Since NP-Complete is in NP ...
3
votes
1answer
78 views

Trouble understanding why Disjunctive Normal Form is polynomial time solvable but not CNF.

So from my understanding when looking at a Boolean formula in Disjunctive Normal Form, its satisfiability is decidable in polynomial time, yet this isn't the case for CNF. Is this because with DNF you ...
0
votes
0answers
40 views

Prove these problems are polynomial time equivalent.

Given a graph $G(V,E)$. The standard $k$-coloring problem consists in finding a feasible coloring (no two adjacent nodes share the same color) of the nodes with $k$ colors. Let this problem be $P_1$. ...
0
votes
1answer
48 views

DAG to $3$ CNF SAT

Given a DAG G, how to reduce it to $3$ CNF SAT to prove it is NP Hard?. Take a Directed Graph, instead of weighted we assign some alphabets to the edges. When we try to find a path from S to T, we ...
0
votes
0answers
64 views

NP hard to NP or P type problem

I am designing a security protocol and to protect my system from DDoS attack. To achieve this I need to define a problem with following characteristics: If the Problem has any unique input from set ...
0
votes
1answer
26 views

How problems in NP and their reductions to one another relate to $\leq_m$(many-one) languages reduction in Theory Of Computation?

So I started to learn theory of computation and in the class we talk about languages and many-one $\leq_m$ reductions. e.g if $A \leq_m B $ then if $x \in A \implies f(x) \in B$ We say that different ...
10
votes
1answer
81 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
34 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
42 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
113 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
80 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
19 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
15 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
78 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
46 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
122 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
43 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
55 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 ...
13
votes
3answers
789 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
144 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
40 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
113 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
35 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 ...
1
vote
0answers
51 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
45 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
15 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 ...