Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
Questions tagged [np-complete]
676 questions
2
votes
1 answer
NP-completeness and difficulty of all possible solutions
Take the SAT problem (or any other NP-complete).
Is the set of all possible combinations of SAT problems are NP-complete?
Or maybe there are combinations that can be quickly solved?
If I take a random logical formula of n variables is always always…
Aurelio
- 479
2
votes
1 answer
Proving NP Completeness
Given $m$ shortest paths between any two vertices of an undirected graph. Determining whether we can pick $k$ shortest paths such that their union covers all edges.
I am trying to reduce set cover problem to it. For a set cover problem we can…
sv_jan5
- 367
2
votes
0 answers
Is 1-in-3 SAT NP-complete if each literal must appear the same number of times as its negation?
Is 1-in-3 SAT NP-complete if each literal must appear the same number of times as its negation? That is, $x_i$ must appear the same number of times as $\neg x_i$ for all $i$.
1-in-3 SAT is a decision problem in which a set of clauses must all be…
user253970
2
votes
1 answer
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 the lecture notes…
Paul A Jungwirth
- 177
1
vote
0 answers
Math Symbols for "Must be Finite"
I want to express the following two sentences in mathematical syntax (if possible):
The number of solutions to the problem should be finite and each solution should be of polynomial length
More difficult (maybe impossible to express in math…
user44191
1
vote
1 answer
How to prove the NP-hardness of this modified set covering problem
In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a minimum cost subcollection of $S$ that covers all…
Fnatic
- 23
- 4
1
vote
0 answers
Find a length 100 cycle in an undirected graph is NP Complete?
Given a graph G with N nodes we need to find if cycle of length 100 exists.
I've been told that this problem is NP-Complete and can be reduced to the Hamiltonian Cycle problem. I believe this is just P.
My first thought was just to perform a DFS on…
nnewtolinux
- 11
1
vote
0 answers
Why finding the shortest solution for a linear Diophantine equation is a NP problem?
I read this paper saying: ...finding the shortest solution for a linear Diophantine equation is a NP problem?
I have two questions:
1). What it means of "the shortest solution" for linear Diophantine equation?
2). Dose it means if we don't purse…
xMath
- 95
1
vote
1 answer
Is this problem NP-complete?
Let matrix $M \in \{0,1\}^{r \times (c+1)r}$ for some $c \in \Bbb Z_{+}$ be given.
Is it NP-complete to decide if $\exists u \in \{0,1\}^{1 \times r}$ $:$$\prod_i v_i \in 2\Bbb Z+1$ where $v=uM$?
Turbo
- 6,221
1
vote
0 answers
Would a runtime of (n choose (n/2)) be considered polynomial?
Simple question, given an input of size n, would an algorithm with runtime O(n choose (n/2)) = n!/((n/2)!(n/2)!), a.k.a. an algorithm which evaluates every possible partitioning of the input into two sets of equal size, be considered a polynomial…
Alex Breeze
- 11
- 2
1
vote
1 answer
Proof that "partition problem in proportion 2:1" is NP-complete
I need to show that problem "partition problem 2:1" is NP-complete.
I know that I need to use $A'$ as certificate to proof that problem is NP.
I know that "partition problem":
given $s: A \rightarrow \mathbb N$, find $A' \subset A : \sum_{a \in A'}…
Angelika
- 69
1
vote
0 answers
Is knapSack 0-1 problem where weights equal to costs is also NP hard?
From wiki:
Given a set of items, each with a weight and a value, determine the
number of each item to include in a collection so that the total
weight is less than or equal to a given limit and the total value is
as large as possible
Given that…
Ilya Gazman
- 1,440
1
vote
1 answer
Am I right that it takes $(\operatorname{length}(S)/3)/\operatorname{length}(C)$ odds of finding a solution for Exact Three Cover if one exists?
Consider I have $S$ elements $1,\ldots,3000$.
And $30,000$ $3-sets$ in $C$.
(eg.$C = [[1,2,3],[4,5,6]\ldots]] 29,998 \text{ more to go}$)
This I find really strange. A solution has $\operatorname{length}S/3$ units. Our solution must have $1000$…
Dingle Berry
- 35
1
vote
2 answers
Max Clique - NP Problem
The question is to show that the recognition version of Clique is in NP.
I have started with a graph G=(V,E) and integer k such that G does have a clique C of cardinality k. How to proceed further from here?
Thanks in advance for any help.
deial
- 11
1
vote
1 answer
Transforming searching to SAT(isfiability)
I'm having problems trying to understand a powerpoint our teacher gave us. The topic is on the theory of NP-Completeness. My biggest questions are,
1. How does the author derive all the 8-22 statements simply from 8-21?
2. How does the author change…
