Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
15
votes
1answer
2k views
Why are there only a few known Ramsey numbers?
Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test?
...
0
votes
0answers
17 views
The problem category of sudoku Puzzle solved by search algorithms
Good day everybody,
Sudoku puzzle solvers have been categorized in the literature to:
Deductive algorithms that perceive sudoku as a hard constraint satisfaction problem (CSP) or Boolean ...
-1
votes
1answer
46 views
NP vs CO vs P Problem
if we assume
set of all tautology in predicate logic, with above assumption is :
1) NP Complete?
2) NP but not NP- Complete?
3) CO-NP Complete?
4? CO-NP but not CO-NP Complete?
i ran into a ...
1
vote
1answer
43 views
Prove that the “even” subset sum problem is NP-complete
I need to prove that the even subset sum problem is NP-complete.
"Given a finite set of natural numbers and an even number $n$, decide whether a
subset of the given set exists such that the ...
1
vote
0answers
21 views
Decidability of $P = NP$?
(Please, don't sign this as duplicate of this question, they are not.)
Is it possible, that the well-known $P=NP$ conjecture is undecidable in ZFC?
Is there any result about this topic?
1
vote
1answer
17 views
Trying to prove something in complexity
I just started to learn about complexity-theory, and I'm trying to prove this:
If P=NP, then every (non-trivial) language in P is NP-complete.
Can someone give me a solution please?
1
vote
0answers
51 views
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 ...
3
votes
2answers
98 views
Proof that SAT is NPC
I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem).
I read the proof with all its parts corresponding to the Turing machine TM solving it (TM ...
1
vote
1answer
70 views
Mixed Q horn SAT
I am familiar with Horn formula: Formula whose clauses have atmost one positive literal.
I am also familiar with Mixed Horn formula: Formula whose clauses are either 2 CNF or Horn.
Question 1: But, ...
1
vote
1answer
46 views
Existence of a trail of given length in a graph - NPC?
I am trying to determine, whether the problem of a trail of given length in a graph is a NPC problem.
We have a graph $G = (V, E)$ and $k \in N^+$. Does this graph contain a trail of length at least ...
0
votes
0answers
24 views
Independent Sets that are Odd Covers
I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
1
vote
1answer
25 views
Polynomial Reduction for restriction
I ran across a polynomial reduction that used the fact that one language was a restriction of the other. Is that statement really true?
$$
L_1 \subseteq L_2 \rightarrow L_2 \leq_{p} L_1
$$
Thanks!
1
vote
1answer
43 views
Relation of encryption to P, NP, and NP-Complete
After watching a Harvard Lecture regarding the understanding of P, NP, and NP-Complete,they also talk about our encryption algorithms being cracked or useless once we solve the mathematics side of it? ...
0
votes
1answer
88 views
P, NP-Complete and NP-Hard Problems
I have confusion over P, NP-Complete and NP-Hard problems.
I understand a polynomial time algorithm is one which can be solved for a an input string of length n. But why would a problem not be in ...
0
votes
1answer
28 views
Prove language is in $NP$ without using a reduction
I've been stuck on this question for hours, can't seem to figure this out.
$L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
0
votes
2answers
56 views
What does psuedo-polynomial algorithm for subset sum problem mean?
Help me out here - just trying to better understand what 'psuedo-polynomial' means...
If the input to an NP-Complete problem is 100 items(ie n=100), and the 'target' is the actual value '100'(t=100): ...
2
votes
1answer
62 views
Prove 2-HamiltonianCycle $\in \textbf{NP}$
Just want to verify that I have the right idea here with this hamiltonian cycle question.
$HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
0
votes
0answers
24 views
Proof: $\alpha \mid p_j=1,r \mid \gamma$ is at least as easy as $\alpha \mid r_j, pmtn \mid \gamma$
I have to prove the following: show that the problem $\alpha \mid p_j=1,r_j \mid \gamma$ is at least as easy as the problem $\alpha \mid r_j, pmtn \mid \gamma$ if all processing times and release ...
0
votes
3answers
68 views
Gaining Mid-level Understanding of P vs NP
I have a base understanding of N and NP, but I want to find some material to gain a better understanding to it. E.g. 'Mid-level', something that goes more into depth of it. Any suggestions for PhD ...
0
votes
1answer
130 views
Chaos Theory and Sum Subset Problem
In respect to the "P versus NP" controversy, can't chaos theory be used to solve problems like the Sum Subset Problem with non exponential performance?
Like, chaotic equations, are like paths to very ...
6
votes
1answer
676 views
Why is Dantzig's solution to the knapsack problem only approximate
For a bunch of items with values $v_i$ and weights $w_i$, and with a total weight $W$ that our bag can carry, how do we achieve maximum total value without breaking the bag? Dantzig proposed that we ...
0
votes
0answers
14 views
In the definition of NP, is it required to have polynomially bounded length of certificate?
So given the definition in our lectures, we were told that NP is defined as the set of languages $L$ s.t. there exist a polynomial time bounded Turing-acceptor M s.t. $L ={w: M accepts(w#c) for some ...
0
votes
1answer
41 views
Optimization problem for feeding the hungry
So I am trying to solve a problem. I believe it is $NP$.
Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
0answers
43 views
Proof for ACYCLIC PARTITION being an NP-complete problem
I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.
I'm interested in reading any proof of ACYCLIC PARTITION (Garey and ...
0
votes
0answers
51 views
What is an algebraic expression over a field structure?
I am working on a problem, and I am not understanding the language very well. Here is the setup of the problem:
Consider the set $\{ 0, 1, 2 \}$ with the operations addition $(+)$ modulo $3$ and ...
1
vote
2answers
92 views
Which pure mathematical problems could be tackled with an algorithm solving NP-complete problems?
In the past, practical applications have motivated the development of mathematical theories, which then became the subject of study in pure mathematics, where mathematics is developed primarily for ...
0
votes
0answers
36 views
path of length >=k in polytime in bipartite graph
I am trying to find whether it is possible to find a path of length greater than or equal to k, given the starting and ending vertices, in a bipartite in polynomial time, or whether this is NP-hard. ...
0
votes
0answers
43 views
How do I reduce 3-SAT to a 3-SAT NAE problem?
I am trying to figure out how to reduce a 3SAT problem to a 3SAT NAE (Not All Equal) problem.
Not only that, I also figure out that I am not so sure about the reduction to 3SAT either.
Anyway, how ...
2
votes
1answer
24 views
NP question - how to reduce this Graph problem?
I am losing my head on Algorithms (namely P-NP stuff) and I thought I would pop over here.
I have a question: in my last exam (which went rather bad :/ ) there was a question which was on the line ...
0
votes
1answer
21 views
seat every club member np problem
A University has n clubs, the largest of which contains m members (students can be members of multiple clubs). The President of the University wishes to hold a dinner in honor of such student ...
2
votes
2answers
63 views
np or np complete proof of a factory problem
Good evening everyone;
I face with this problem and I could not find a way to proof it. Here is the problem;
A={Writing out the factorial of a number in unary NP-complete or NP-hard (e.g. n! = 11 ...
0
votes
1answer
31 views
should we try to solve problem in np class
Good afternoon everyone;
I am having difficulties to discriminate between NP and NP completeness. For instance, we know that a problem is in NP class should we try to find a algorithmic solution for ...
1
vote
0answers
39 views
Is Quadratically Constrained Quadratic Program (QCQP) in NP?
The general version of QCQP is NP-hard, but is it also NP-complete? That means, is there a non-deterministic algorithm, which solves QCQP in polynomial time complexity?
If the general version of QCQP ...
2
votes
2answers
67 views
Minimum number of elements needed from n sets
Suppose that we have n sets. They may or may not have common elements. How can we find the minimum number of elements that we should pick so that we have at least one element from each set?
For ...
0
votes
1answer
120 views
Proof of: if L is NP-Complete then its complement is coNP-Complete
I have trouble understanding why we need to construct a function to do the following proof and how the function shows that $A \leq_{p} L$:
Claim: If L $\epsilon$ NP then $\overline{L}$ is ...
10
votes
1answer
166 views
Is it possible that P != NP cannot be proved?
I am probably asking a stupid question but what I gather from a layman explanation of Godel's incompleteness theorem is that it is completely possible that a true statement cannot be derived from ...
2
votes
1answer
106 views
Finding no-self-intersecting path in geometric graphs
Is there a polynomial algorithm to determine whether there exists no-self-intersecting path between given vertices $s$ and $t$ in a geometric graph $G$?
Geometric graph is an image of a graph on a ...
5
votes
2answers
201 views
NP-complete: One proof to rule them all
To prove a decision problem $C$ is in NP-complete, 2 things need to be shown:
There is a polynomial verification for $C$ solution.
Every problem in NP is reducible to $C$ - You can solve all the ...
5
votes
5answers
485 views
How to prove that $P \neq NP$
How to prove that $P \neq NP$?
To prove that $P = NP$ all we need to do is to solve one NP-Complete problem in polynomial time for any input, and because all the NP-Complete problems have reduction ...
1
vote
0answers
77 views
How to prove the NP-hardness of this scheduling problem
Suppose there are a set of $m$ jobs $J= \{J_1, J_2, \ldots, J_m\}$ and $n$ machines $M=\{M_1, M_2, \ldots, M_n\}$. Each job $J_i$ consists of $k_i$ unit operations, and there are totally K operations ...
0
votes
2answers
219 views
What is wrong with this proof: P = NP using polynomial solution for UHP
I am going to show you a proof for P=NP, please tell me where I am wrong.
Working space: Symmetric(the distance from AB is equal to BA) Graph with N nodes and M edges.
Goal: find a Hamilton path.
...
0
votes
1answer
62 views
Algorithm for valid 3 coloring.
If we have P=NP, how can I show that a polynomial algorithm exists that given any 3 colourable graph produces a valid 3 colouring (no two adjacent vertices share the same colour)?
1
vote
2answers
75 views
Why do Integer Relation Algorithms (e.g. PSLQ) not solve the subset sum problem?
I'm trying to understand what mistake I'm making or what incorrect information I fail to recognize as such.
The subset sum problem (given distinct $a_i$ and $A$, does any subset of ${ a_i }$ sum to ...
1
vote
2answers
142 views
Why is the decision problem of the “Travelling Salesman” $\in \mathcal{NP}$?
One of the most well-known problems that belongs into the class of $\mathcal{NP}$-complete problems is the Travelling Salesman Problem. However, I fail to see why it is "so obviously" in ...
0
votes
1answer
61 views
DNF-Equivalence Problem
I have the following Equivalent DNF problem:
Input:Two DNF formulas, $F_1$ and $F_2$,with variables $a_1,a_2,...a_n.$
Output: $1$ if $F_1$ and $F_2$ are equivalent, $0$ otherwise.
$F_1$ and $F_2$ ...
1
vote
1answer
105 views
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 ...
1
vote
1answer
43 views
Does the way a graph $G$ is encoded affect the proof that $CLIQUE$ is in $NP$?
For a proof that $CLIQUE = \{ \langle G, k \rangle | G$ is an undirected graph with a $k$-clique. $\}$ is in $NP$ by constructing a nondeterministic Turing machine $N$, where
$N$ = $``$On input ...
3
votes
2answers
169 views
Simple problem whose approximation ratio is still open.
I am preparing for a talk on "Approximation Algorithms", aimed at undergraduate students. In order to motivate the topic, I want to give them an example of a problem which is easy to describe and has ...
-3
votes
1answer
417 views
Is solving the PvsNP example question a solution to PvsNP?
This example question was created by the claymath institute. The PvsNP question states, suppose the dean leaves you with a task to house a group of 400 students inside dorms. But there is only enough ...
0
votes
1answer
39 views
Fastest path to cover area
How do we determine the fastest path to cover an area using an object of some radius r? E.g. a machine that needs to spray a chemical onto a surface. I assume this is some kind of NP-hard problem.
