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
1
vote
1answer
31 views

Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and ...
0
votes
1answer
29 views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

Suppose there is a polynomial time reduction from problem $A$ to $B$. Why is the following false? If $B$ is NP-hard then $A$ is NP-hard. Can some explain this intuitively?
0
votes
2answers
69 views

Is Bitcoin mining NP-Hard?

I can't find this anywhere online. Is bitcoin mining NP-Hard? If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.
2
votes
1answer
24 views

Clarifying the definition of reduction with regards to NP-complete problems

In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a ...
2
votes
2answers
77 views

Maximize number of subsets

Given a list of subsets $S_1, \ldots, S_n$ of the universal set $U = \{e_1,\ldots, e_m\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S_i$. In another words, $...
2
votes
1answer
26 views

$k$-SAT completeness proof when $k$ is linear in number of variables

I'm looking at a special version of SAT in which each clause has exactly $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case? I tried reducing 3-SAT ...
1
vote
1answer
20 views

Is this “superset existence” problem NP-complete?

The "Superset Existence Problem": Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets? To me, ...
2
votes
2answers
65 views

Find maximal clique consisting of at least half of the vertices

Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
1
vote
1answer
84 views

NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find ...
0
votes
1answer
38 views

Reduce Clique to N-Degree-Clique

I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \...
1
vote
1answer
52 views

Understanding P vs NP

I want to make sure my understanding on P vs NP is correct. I know that NP-complete problems cannot be solved in polynomial time, and if P != NP, then all problems in NP cannot be solved in polynomial ...
2
votes
1answer
42 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
1
vote
1answer
32 views

Cyclic tour minimizing total weight

I asked the following question on math.se but it wasn't really answered so moved it over here as I feel it's more relevant. I saw the question below on an old stack exchange question when looking to ...
1
vote
0answers
29 views

Difference longest path problem and underlying decision problem [duplicate]

I am studying the longest path problem with the final objective to show that it is NP-complete. On wikipedia I read that the problem itself is NP-hard but the underlying decision problem is NP-...
2
votes
1answer
48 views

Difficulties proving when a language is in P or is NP-complete

I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$: $L_1 = \{...
-2
votes
1answer
70 views

How does one sketch a proof to show that the following problem is in the P Complexity Class?

I have the following problem. I do not know where to start or how I should approach this problem. I am not sure about how to prove if a problem is in a complexity class of P . I know how to do NP but ...
0
votes
0answers
20 views

How many strings for CLOSEST STRING lower bound to apply

In the CLOSEST STRING problem, one is given (bit-)strings $s_1, \dots, s_t$, each of length $L$ and an integer $d$. The question to be answered is whether there exists a string $s$ that has hamming ...
0
votes
1answer
74 views

4 Vertex Cover Problem is not NP Complete why?

With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?
0
votes
1answer
27 views

maximum Hamilton cycle and NP-completeness

we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?
0
votes
1answer
33 views

How to prove that the subset sum problem is polynomially reducible to the knapsack problem

I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete. There are two parts to showing knapsack is NP-...
0
votes
0answers
39 views

Is the Maximum Independent Set problem NP-complete? [duplicate]

It can be read on Wikipedia that MIS is NP-hard. However, is it also NP-complete? This article says: "Thus, the Maximum Clique Problem(MCP) and the Maximum Independent Set(MIS) Problem are ...
1
vote
1answer
12 views

checking time for a circuit of size in polynomial k

On the page 1073 of CLRS(Introduction to Algorithms), Given a circuit C, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. ...
0
votes
1answer
58 views

“If any problem in NP is not polynomial-time solvable, then no NP-complete problem is polynomial-time solvable.”

This is given vertabim in my lecture slides and it seems like I'm having difficulty proving this statement mathematically. I know that P is a subset of NP and NP-Complete is also a subset of NP. But ...
-1
votes
1answer
25 views

NP-complete problem of partitioning into several sets with a Hamiltonian cycle

How to prove the $NP$-completeness of the language $L$ = $\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so, that ...
0
votes
2answers
52 views

How to reduce the original partition problem to one of its variation?

Here's a statement of the set partition problem: The set partition problem takes as input a set $S = \{ a_1, a_2, ..., a_n \}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ ...
0
votes
0answers
36 views

How to create mathematical proof of TSP and SLAP equivalence?

In my thesis, I'm dealing with SLAP (storage location assignment problem) -- which is finding optimal distribution of products to location slots in a generic warehouse. My aim was to implement ...
1
vote
1answer
57 views

P-NP related 3 sub-problems

This is a question on a practice final. Which of the following statements are true? If it is false, what is the underlying reason behind that? I. If 3-CNF-SAT is in P, then Clique is also in P. II. ...
0
votes
0answers
28 views

Gain the Mastery of prooving NP Complete Problems [duplicate]

I want some piece of advice on how can I improve my capability of proving NP-completeness of problems. I am well known with all the concepts theoretically but when it comes to solving down, I get ...
0
votes
1answer
37 views

DNF and CNF and Complexity Theory

$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$. If that case is true and the conditions ...
2
votes
1answer
324 views

The situation when P is a superset of NP

Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?
0
votes
1answer
16 views

Can a classical supercomputer solve a large Max-Cut Problem?

The Fugaku is the most powerful computer. Its performance is 442,010 TFlop/s. That number does not mean much to a layman like me. I want to know how fast it can solve a hard problem. For example, can ...
1
vote
1answer
28 views

3Col reduction Variation, Special edges

I have a question concerning NP reduction. My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding ...
0
votes
1answer
78 views

Proving NP-completeness for a not so cheesy problem

Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. ...
2
votes
0answers
47 views

Why do I only need to reduce from one problem in NP to prove NP-Hardness?

Suppose I wish to show that my decision problem $Q$ is NP-Hard. Why do I need to reduce from one problem $Q'$ of known hardness ? Consider for instance the following situation: Here, I have my set NP ...
4
votes
1answer
49 views

Can a computational complexity class be redefined by using any complete (decision) problem?

Let $\mathcal{C}$ be a basic complexity class (such as $\mathrm{NP}, \mathrm{PSPACE}$). And $\mathcal{C}$ is closed under a reduction "$\leq$" (such as polynomial time many-one reduction &...
0
votes
0answers
26 views

Proof that n-dependent Set in Graph theory is NP Complete

Consider an undirected graph $G$. A subset $S \subseteq V(G)$ is n-dependent if for every $x \in S, d_{<S>}(x) \leq n-1$. The n-dependence number of $G$, denoted $\beta_n(G)$, is maximum ...
-1
votes
1answer
46 views

If A is not in NP, and A reduces to B, does this mean B is not in NP?

I know it is true that if A is not in P, and A reduces B, then B is not in P. But is it true for NP as well? If A is not in NP, and A reduces to B, does this mean B is not in NP? Why or why not? ...
7
votes
1answer
908 views

Is there a simple argument why graph isomorphism is not NP-complete?

I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete. I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of ...
2
votes
0answers
35 views

Is there a super-linear lower bound on the time complexity of all solutions of NP complete problems?

$P \ne NP$ would imply that any polynomial is a lower bound on the time complexity of any NP complete problem. Is some non-trivial lower bound known at all?
0
votes
0answers
65 views

3-Sat reduction to facility location problem

I'm learning about NP problems and I this problem which is a bit challenging for me. You are given an undirected, simple graph G = (V,E) and an integer k where nodes represent cities and edges ...
0
votes
0answers
100 views

How to Show Subset Sum $\le_p$ 3-Partition

Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. Is it ...
0
votes
0answers
15 views

Showing that Subset Sum Reduces to 3-Partition [duplicate]

Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete. This is a ...
0
votes
1answer
39 views

Reduce Subset-Sum to Sat

Is there a reduction from SUBSET-SUM to SAT? Just general SAT, not 3-SAT. Also the given multiset S only has positive integers. SUBSET-SUM is defined as follows: Input: a multiset S = { x1 , ... , xn }...
0
votes
0answers
26 views

Set partition with an allowable difference

I have a variation of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is ...
1
vote
0answers
19 views

3-OCC-MAX SAT np-complete?

Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this ...
1
vote
2answers
204 views

NP-completeness of testing whether a SAT formula does not contain any redundant clause

This paper explains that testing the irredundancy of a SAT instance is NP-complete. But I don't understand the theorem/reduction. How would one reduce 3SAT or k-SAT to this problem, for example?
0
votes
0answers
57 views

4SAT $\leq_p$ NAE4SAT

Given the SAT problem, the NAE (not all equal) SAT adds the restriction that there must exist two literals in a clause which have different truth values in a satisfying assignment. We can show that ...
1
vote
0answers
30 views

Is Partition Problem with non-integer input NP-complete?

The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$? I have read a lot of proofs using ...
2
votes
0answers
40 views

Examples of exponential time linear space exact algorithms

I am looking for examples of NP-complete problem-solving exact algorithms with a linear space complexity and an exponential time complexity. Algorithms which solve the k-SAT problem exactly (such as ...
-1
votes
1answer
31 views

What are the practical examples of Semidecidable problems? Is NP problem a semidecidable problem?

I am going through a Turing machine topic. I know about decidable, semi decidable, and decidable problems. But honestly speaking, I did not get any practical examples of Semidecidable problems. Can ...

1
2 3 4 5
26