Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

Filter by
Sorted by
Tagged with
0
votes
1answer
18 views

Reduction of np to npc

Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq_p^\mathsf{}A$ then $D$ is $NPC$" is true or not? My approach: Since $D\leq_p^\mathsf{}A$, therefore $...
1
vote
1answer
173 views

NP-completeness of satisfiability of formula over 50 variables

Given a boolean formula $F$ of length $n$ defined over a fixed number of variables (say 50), is it NP-complete to decide whether $F$ is satisfiable?
1
vote
1answer
27 views

Can one show NP-completeness by showing a reduction to 3SAT?

The standard technique to show NP-completeness of $L$ seems to be to show that $L$ is in NP, and then to show that some NP-complete language can be reduced to it. What if one tried to show it the ...
4
votes
1answer
111 views

Is there a 3-SAT problem in less than 100 variables that no one has been able to solve?

In number theory progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability? ...
0
votes
0answers
15 views

Complexity class of computation of Homfly polynomial

It is claimed that "the problem of the computation of the homfly polynomial is NP-hard." but is it known if it is NP-complete? By the definition of NP-completeness, wouldn't it be enough to ...
4
votes
1answer
613 views

Proofs of reduction of any hard problem

Approach:1 To prove any unknown problem $B$ is NPH then take any known NPH problem $A$ (e.g. $3$-sat) which reduces to $R$ in polynomial time. If I take any instance example $I_1$ of $A$, then ...
0
votes
1answer
80 views

If $A\leq_m^\mathsf{}B$ and $B$ is a regular language, does that imply that $A$ is a regular language?

Corollary:1 We know that if $A\leq_m^\mathsf{}B$ and $B$ is decidable then $A$ is also decidable. This is because if there exists a specific algorithm for solving $B$ and we can also reduce $A$ to $B$ ...
0
votes
0answers
21 views

Given a graph and specific VC instance, find number of variables when reducing from VC to SAT

I have question already answered from past exam, and I'm trying to figure where my logic fails. Given a graph find vertex cover of size 2. The question is how many variables are there going to be for ...
2
votes
1answer
46 views

How hard is random SAT?

There is plenty of research into the so-called "random SAT" problem, where we basically try to solve SAT instances with clauses chosen "at random" in some sense. There are all ...
0
votes
1answer
74 views

Reduction from undecidability, decidability to decididabilty

If given any two language both $L_1$ and $L_2$ are decidable then why both $L_1\leq_m^\mathsf{}L_2$ and $L_2\leq_m^\mathsf{}L_1$ are false. Please provide easy explanation with any counterexample ...
1
vote
0answers
21 views

Software/library to generate Ising models for random $k$-sat problems

Could someone point me to a software/library which lets one to generate the Ising model/spin model for random $k$-sat problems or $k$-sat problem of a given structure? I understand that it will be ...
-1
votes
1answer
28 views

K-Path-Problem is in $P$ or $NPC$

Given an undirected graph $G(V, E)$, two vertices $u$ and $v$ and a natural number $k$, does a path of at least length $k$ exists between these two vertices? How can we solve this problem? I think ...
1
vote
1answer
20 views

Consequences of a polytime algorithm for a decision problem reducible to 3SAT

If there is a polynomial time algorithm for a decision problem $A$, which is m-reducible to 3SAT, and 3SAT is NP-complete, does this prove that P=NP?
1
vote
1answer
71 views

Is this variant of the pinwheel scheduling NP-Hard?

I wonder if the following variant of the pinwheel scheduling is NP-Hard. Given a set of n radars S = {s$_1$, s$_2$... s$_n$} and a set of m areas A = {a$_1$, a$_2$, ... a$_m$}. Each radar s $\in$ S ...
0
votes
0answers
24 views

Number partition subjected to the cardinality of subset

I hope someone can take some time to consider the following problem and welcome to discuss together. Number partition problem is one of well-known NP-hard problems. Now I am considering the hardness ...
2
votes
0answers
31 views

Under ETH: $\exists$ Problem unsolvable in $2^{o(n)}$ $\Leftrightarrow^?$ 3-SAT can be represented in linear bits

It is a popular open question if there is a problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH. I recommend reading that question first. That question states that, assuming the ETH ...
3
votes
1answer
31 views

Does padding with dummy bits allow an NP-problem to be solved in fast exponential time?

Take this example mentioned here: NP-hard problems with very fast exponential-time algorithms We can create such problem by padding assuming ETH‌. Take an NP-complete problem $L$ such that $L$ is ...
0
votes
1answer
25 views

If problem A reduces to an NP-Complete problem B, can we say that A is in NP?

I was reviewing All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete? I understand that the general way we show a problem A is in NP is to show there exists a poly-...
0
votes
0answers
17 views

Is job shop scheduling J|pij=1|Cmax is still NP complete?

Is the job shop scheduling, where the processing time is 1 time-unit for all operations ($J|p_{ij}=1|C_{max}$), still NP complete or not? Are there any literatures that have a proof?
-2
votes
2answers
50 views

Is A and C NP-complete?

Given 3 decision problems in $NP$: $A,B,C$. Consider that there are $2$ reduction algorithms, one is $A\le_p B$ (with run-time $n^{10}$) and the other is $B\le_p C$ (with run-time $n^5$). If $B$ is $...
1
vote
1answer
20 views

Three dimensional matching expressed as SAT

The posting in the website Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING seeks $3SAT$ as a $3$ dimensional matching instance. I am looking to solve the converse problem. How to solve three ...
1
vote
2answers
122 views

Is this explanation confusing NP-hard and NP-complete?

My notes on P vs NP say the following: Every problem x in the NP-hard class has the following properties: – There is no known polynomial-time algorithm for x. – The only known algorithms take ...
-5
votes
1answer
63 views

Really confused

Suppose there is a language L∈NP, that is not NP-Complete and L≠∅ and L≠Σ∗. Which of the following statements can we infer from this? P = NP P ⊊ NP P ≠ NP NP ⊆ P
0
votes
1answer
34 views

How to prove that the generalized assignment problem (GAP) is NP-hard?

Specifically, what NP-hard problem can we reduce (the decisions version of) GAP to and how do we prove its correctness? The decision version of the generalized assignment problem is to determine ...
3
votes
0answers
38 views

Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do. In short: the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined. The new ...
-4
votes
3answers
79 views

What is wrong with this argument that if A is NP Complete, but B is in P, then A\B is NP Complete and B\A is NP Complete as well?

The following seems to me to be relevant to this question, but to me is an interesting exercise, especially since I have not formally worked with complexity before, but I want to learn more: Suppose ...
-2
votes
1answer
45 views

Reducing subsetsum to {<G, l, u> | G is a weighted graph that has a spanning tree with weight between l and u} [duplicate]

How can I reduce Subsetsum (or maybe other np-complete problem) problem to the problem below? input : a weighted graph $G$ and numbers $l$ and $u$. output : Does $G$ has spanning tree, $S$, such that $...
2
votes
1answer
36 views

Language in NPC and CoNP

A few days ago I had a test that I failed to pass, and it had a question that I failed to do. the question: given: $A \in NPC$ $A \in CoNP$ Determine which of the following statements is correct: $P\...
3
votes
2answers
53 views

Reduction with CoNP and CoNPC

I have a question I was unable to do, from a last test I had. This is the question: Suppose that there is a language $A \neq \emptyset ,\sum{_{}}^{*}$ such that $A \in CoNP - CoNPC$. Determine ...
2
votes
1answer
24 views

Reduction with NPH

I have a question in complexities that I could not do. There will be D, E, F, three languages belonging to NPH. Suppose that the reductions exist $D \leq _P E$ and $E \leq _P F$. Determine which of ...
-1
votes
1answer
37 views

Reduction from SAT to 3SAT

a few days ago I had a test and could not pass it. This is a question I did not understand in the test. Recall the reduction we saw $SAT \leq _p 3SAT$. Given verse $\varphi$ in the form of $CNF$, we ...
1
vote
2answers
146 views

Reduction from vertex-coloring problem to edge-coloring problem

A few days ago I had a test and could not pass it. This is a question I did not understand in the test. We will look at the Edge-Coloring problem, in which, as is well known, we get as input graph G =...
1
vote
1answer
37 views

Why this problem is NP-Hard?

I'm asking about the question described here: Knapsack Problem with exact required item number constraint Can't we iterate over $\binom{n}{L}$ options (which is polynomial), and for each option check ...
3
votes
1answer
55 views

FPT algorithm for Knapsack

I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?
1
vote
0answers
22 views

Research on exact-cover problem and graph theory for NP-complete problems? [closed]

Sorry for the vagueness, but I'm trying to study the latest progress on the exact cover problem and using graphs for NP-complete problems. Googling around has not been very helpful. I understand the ...
0
votes
1answer
39 views

Is this variation of Max-Coverage NP-hard?

Setup An instance of Max-Coverage is typically defined by a collection of $n$ sets $S = \{s_1, s_2, \dots, s_n\}$, and a budget $k$, where the objective is to select a subset $U\subset S$ such that $$\...
0
votes
0answers
22 views

Polynomial Reduction from $3SAT$ to $MSAT$

I am supposed to show that $3SAT$ $\rightarrow$ Every clause hast exact $3$ literals is polynomial reducible to $MSAT$ $\rightarrow$ At least half of every clauses' literals are true Let $F$ be a ...
0
votes
0answers
85 views

Algorithm for Variant of 0-1 Knapsack Problem

Variant of 0-1 Knapsack Problem is when you can choose exactly $k$ items from $n$ items, and $k$ is positive integer parameter that came in the input. Is there an algorithm with running time ...
2
votes
1answer
48 views

Number of queries for $NP^{NP}$

So a few days ago my lecturer told us that for every nondeterministic polynomial time oracle machine $M$, there is a nondeterministic polynomial time oracle machine $N$ that gives us $L(N^{3-SAT}) = L(...
0
votes
1answer
46 views

How to prove Dense Subgraph problem is in NP

I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies ...
1
vote
3answers
127 views

Spanning tree whose sum of edge weights are between two boundries

I saw this problem: $\langle G,w,k_1,k_2 \rangle \in L$ iff Graph $G$ has a spanning tree whose sum of edge wights are less than $k_2$ and greater than $k_1$. The problem says that we can prove this ...
1
vote
1answer
27 views

Computational complexity of dividing a set of constraints into a minimum number of satisfiable clusters

I am looking for the computational complexity of the following problem. Divide a given set of constraints into a minimum number of satisfiable clusters such that the constraints within the same ...
0
votes
1answer
25 views

Efficient structure for pruning on job scheduling

This is an issue I encountered on several applications with different variants. But here is the common base for which I suspect to miss a more efficient approach. There are $K$ different tasks to ...
3
votes
0answers
39 views

NP-complete problem

Is the following line true? Consider three problems A, B and C. If $A$ $<p$ $B$ and $B$ $<p$ $C$ and $B$ is NP-complete problem, then $C$ is also NP-complete. If B is NP-complete, then C would ...
1
vote
1answer
27 views

Time complexity of the triangle factoring problem

We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ ...
0
votes
2answers
94 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
2
votes
1answer
61 views

Must all NP-complete problems have an asymptotically optimal algorithm?

According to Blum's speedup theorem, there exist problems with no asymptotically optimal algorithm. Suppose that NP-complete problems had speedup. We know a problem X with asymptotically time ...
0
votes
1answer
31 views

NP-completeness of variant SAT: SAT-5Clauses

I'm solving Problem 14.4 of What can be computed?. 14.4 Define the decision problem SAT-5CLAUSES as follows. The input is a Boolean formula B in CNF. The solution is “yes” if it is possible to ...
2
votes
0answers
77 views

An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
1
vote
1answer
32 views

Is every pair of NP-Complete problems reduced in polynomial time?

As shown above, several NP-Complete problems are derived from GSAT (general satisfiability problem) by a polynomial-time reduction. Then, my question is that is every pair of NP-Complete problems ...

1
2 3 4 5
28