# Tagged Questions

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

38 views

### The meaning of “set” in NP-complete problem

Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more. The traditional ...
22 views

### Split k sets to 2 groups of sets ,is this np hard? [duplicate]

Given k sets ,each contain several elements . I want to split them to two groups , the first group contains m sets ,the second group contain n sets , m + n = k . Let w1 be the sum of the weights of ...
39 views

### Label coloring to maximize number of “balanced” triangles (NP-hardness)

Define a triangle in undirected graph $G$ is balanced if the edge labels in the triangle are $(+1, +1, +1)$, $(-1, -1, +1)$, $(+1, -1, -1)$ or $(-1, +1, -1)$ (social balance theory). Problem ...
186 views

### Why does restricting size of input for NP complete problem imply a runtime of O(1)?

I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic. The statement is 'If you restrict the input size of the problem then solving that ...
The domination problem $DOM$ is defined as $$DOM = \{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \},$$ and the rainbow domination problem $RDOM$ is defined as $$... 0answers 18 views ### Find reduction from Hamiltonian Cycle to Double Hamiltonian Cycle$$DoubleHC=\{G\,| \text{G has at least two Hamiltonian Cycles}\}$$I think about take a graph with HC and add to it two vertexes and edges to two randomally vertexes, but without success. Is my try ... 1answer 50 views ### I can find in a graph a path between two input nodes to be exactly of length k I have in input an undirected graph and two nodes. It is possible to find a path of lenght k, where k is a constant, in polynomial deterministic times? Or this problem belongs to NPC? Thanks 1answer 45 views ### If the Clique-k Problem is in P, why not Clique as well? I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?) The general clique problem is defined as \text{CLIQUE} = \left\{ (G, k) | ... 1answer 43 views ### Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively? NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ... 1answer 101 views ### Why doesn't subset sum solution violate Exponential Time Hypothesis? The quickest algorithm for solving subset sum currently is 2^{n/2} (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can ... 2answers 109 views ### What would NP-complete solution in O(2^N/B) mean? Suppose we had an algorithm that solved an NP-complete problem (SAT, TSP, etc.) in time O(2^{N/B}) where B>2 is an input to the algorithm, along with the instance to be solved. So for B < ... 1answer 27 views ### Poly-time reduction from HAMPATH to HAMPATH-E I need to prove that HAMPATH-e = { < G,s,t,e > | G is directed graph, s, t are vertices and e a edge } there is hamiltonian path between s to t that cross the edge e is an NP complete. i've ... 1answer 33 views ### Knapsack: there is a polynomial solution in bit terms? I'm reading about Knapsack problem. The approaches to solve that I found: Branch and bound Brute force Dynamic programming Memory functions Greedy All solutions have exponential time in terms of ... 0answers 40 views ### prove that the satisfiability problem with each clause containing at most 3 literals, denoted by ≤3SAT, is NP-complete I've tried to prove it for several days but I can't make sure if it is equivalent to max-3-SAT problem? This problem seems similar to the proof of SAT ∝ 3-SAT except the case where there are more than ... 2answers 84 views ### What are the hardest problems that are in P if and only if P=NP? I used to think that NP complete problems are the "hardest" problems of all problems that would still be in P if P=NP. Now I think otherwise. What I'm asking is if there are any problems that are ... 1answer 66 views ### Why is Knapsack and ILP NP-complete I have a question concerning several NP-hard problems and why they are (or are not NP-complete). I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and ... 2answers 71 views ### What is the simplest known NP-Complete problem for testing P=NP solutions? [closed] About a year and a half ago I ask this question regarding P=NP. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic. With that stated, ... 3answers 2k views ### Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP? Basic sanity check on NP-complete solutions: Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively ... 1answer 20 views ### How do I show this variant of the longest path problem is NP-hard? The problem is as follows: "Given a weighted graph G and a path p, show that p is the longest simple path in G." I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my ... 2answers 307 views ### Is this an instance of a well-known problem? Context I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I ... 2answers 101 views ### How are games like chess provably harder than NP? From this question, I had the debate about how problems harder than NP are proved. I said that intuitively I understand it as (from this video explaining that some problems are provably harder than ... 0answers 26 views ### If problems P1 and P2 are known to be NP-hard, then we can conclude that P1∝P2 and P2∝P1? [duplicate] I know the definition of NP-hard is that “a problem(P1 or P2) is NP-hard if every NP problem could be polynomially reduce to (P1 or P2)”. However, P1∝P2 means P1 could be polynomially reduced to P2, ... 1answer 43 views ### Can we reduce an NP complete item to an NP item which is \bf{non} P? I'm curious if we can reduce an NP-complete problem to an NP problem which is not a part of the P set. Meaning, can we take an algorithm for this kind of NP problem and use it to solve a ... 1answer 125 views ### How to use an old SAT solver to discover a new one, as is done in The Golden Ticket? In Lance Fortnow's book The Golden Ticket, he mentions that once you have a polynomial-time algorithm for an NP-complete problem, you can use it to find a faster algorithm. Can you tell me how that is ... 1answer 183 views ### How do we know for sure that EXPTIME ≠ P? I'm a beginner in learning about computational complexity and this has stumped me. I've read that by the time hierarchy theorem, it's known that EXP-complete problems are not in P. (Wikipedia) It ... 1answer 34 views ### Flaw in linear programming solution for multi-commodity flow problem? The multi-commodity flow problem problem statement - wiki According to constraints of multi-commodity flow problem a given material must start at source s with demand d and end up at its target t. ... 2answers 470 views ### Reconciling NP and the decision problem So I've seen that most NP-Complete problems seem to take the form of decision problems - problems which require only a yes/no answer. However, how can this be reconciled with the requirement that the ... 0answers 58 views ### Reduction of 3-SAT to Vertex Cover? Can someone explain to me in the most simplest possible way, how to reduce 3-SAT to Vertex\:Cover ? I am following the explanation here(scroll to page 4 bottom). I understand the basic setup of ... 2answers 137 views ### Time complexity of a problem inspired by palindromes This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings [v_i, v_2, ... ,v_n] where \Sigma |v_i|  is even number. ... 0answers 49 views ### How do you reduce graph edge colouring problem to the graph node colouring problem I know that if the nodes of a graph can be coloured by n colours such that no two nodes sharing an edge have the same colour, I can also colour its edges with n colours such that no two different ... 1answer 53 views ### Turing NP complete but not Karp NP complete? Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction? Conversely is there some examples of candidate problems that have Turing reduction to SAT ... 1answer 33 views ### Finding top k which are the most different from each other Assume I have a set of items A and each item a \in A has a score s(a). Also, each two items a_1,a_2 \in A have variety score var(a_1,a_2) which tells how different they are. I want to ... 1answer 61 views ### Why is determining if there is a solution to a Battleship puzzle NP-Complete? This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't ... 0answers 41 views ### find a minimum-cost pair of arc-disjoint paths, both within a given restricted distance Is there a polynomial algorithm that can find a pair of arc-disjoint paths in a directed graph that has a minimum total cost, subject to the condition that both paths are within the same distance. ... 3answers 145 views ### What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete? Finding genus of a biparite graph is NP-complete and finding genus of a degree 3 graph is NP-complete and so finding genus of a degree 3 bipartite graph is NP-complete. Though implication ... 3answers 846 views ### Can any finite problem be in NP-Complete? My lecturer made the statement Any finite problem cannot be NP-Complete He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of ... 2answers 74 views ### Is the “modular subset product” problem NP-complete? While examining some NP-complete problems relating to sets of integers, a question flashed through my mind: whether the NP-completeness of these problems is retained when integer arithmetic is ... 1answer 40 views ### How can ships in Battleship be partitioned into B subsets, each with a capacity C? I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: http://www.mountainvistasoft.com/... 1answer 47 views ### What is the time complexity of Summing Triples with duplicates? Summing Triples problem is strongly NP-complete as shown by McDiarmid. Summing Triples problem: Input: list of 3N distinct positive integers Question: Is there a partition of the list into N ... 1answer 55 views ### show that special case of NP-complete problem is also NP-complete? I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure ... 1answer 41 views ### Maximize function over a set with a transitive and antisymmetric relation Let \mathcal{R} be a transitive and antisymmetric relation defined over a finite set X. For any set S\subseteq X define \Gamma(S)=\left\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\... 1answer 46 views ### What does Cellular Automata Pre-image problem actually means? I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata. In the 2nd page he lists three NP-Complete ... 0answers 26 views ### Reducing partition to a partition where sum(partition1) = 3 times sum(partition2) Given the following NP-complete problem: PARTITION Input: A list of positive integers a1,a2...,an Question: Can the list be partitioned into 2 parts, A1 & A2 such that the sum of each part is ... 1answer 21 views ### About the interpretation of the SOS hardness results of the planted Max-Clique problem One can look at these two papers http://arxiv.org/abs/1502.06590 and http://arxiv.org/abs/1507.05136 and see their main theorems. If I understand right then both these papers are talking of the ... 3answers 82 views ### Size of instance after reduction A decision problem C is NP-complete if C is in NP, and every problem in NP is reducible to C in polynomial time. Reduction means transforming an instance of one problem A to an instance ... 1answer 101 views ### Implication of Berman and Hartmanis conjecture I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture : All NP-Complete languages are p-isomorphic. Then the book says that ... 0answers 20 views ### A particular type of SOS hardness proof Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical x_i^2 =1 ... 1answer 49 views ### If a language is X-complete, is its complement is X-complete as well? I'm looking for an information about closure of complexity complete classes. Is it true that any language, if the language is X-complete, then its complement is X-complete? Why? I was thinking ... 1answer 101 views ### Is this a well-known NP-hard problem? Let R = \{1, \ldots, n\} and S = \{S_1, \ldots, S_m\} a collection of subsets of R such that R = \bigcup_{i = 1}^m S_i and, for n > 3,$$3 \leq \vert S_i \vert \leq 4 \, , \enspace i \in \...
Consider the unweighted and weighted versions of the vertex cover problem (UVC and WVC for short, respectively). As UVC is a special case of WVC, is it true that \text{UVC} \leq_\mathrm{m} \text{WVC}...