mapping,combinatorics,computation-theory,np-complete,set-theory

You could create a bipartite graph in the following manner: For each element in the set X create a node in the U disjoint set of the graph For each subset in the set S create a node in the V disjoint set of the graph If element of X...

complexity-theory,np-complete,np

From a formal languages perspective, there are only countably many problems in P and uncountably many problems not in P. Every problem in P can be solved by a deterministic, polynomial-time Turing machine, and since the number of TMs is countably infinite, the number of languages in P is countably...

algorithm,graph-theory,dijkstra,np-complete,hamiltonian-cycle

No, this is not possible. Your simplified problem is still NP-hard. A reduction from travelling salesman: Given a graph (V, E), find the shortest path that visits each v in V exactly once. Take an arbitrary vertex v in V. Split v into two vertices v_source and v_sink. Use your...

algorithm,np-complete,subset-sum

I would recommend doing this reduction in two steps. First, reduce subset-sum to the partition problem. This problem is related to subset-sum, except that instead of being given a target k, the goal is to split the set into two exactly equal halves. This isn't too hard (I'll leave it...

algorithm,big-o,dynamic-programming,partitioning,np-complete

A naive, trivial and still pseudo-polynomial solution would be to use the existing solution to subset-sum, and repeat for sum(array)/2to 0 (and return the first one found). Complexity of this solution will be O(W^2*n) where W is the sum of the array. pseudo code: for cand from sum(array)/2 to 0...

computation-theory,turing-machines,np-complete,np,decidable

This statement is false. Since 3SAT is NP-complete, every problem in NP polynomial-time reduces to 3SAT, so if you choose any language in NP, then it will polynomial-time reduce to 3SAT. In particular, if you choose the empty language ∅, which is known not to be NP-complete, then ∅ ∈...

reduction,np-complete,np,clique-problem,independent-set

I found out reduction from problem INDEPENDENT-SET to CLIQUE-OR-INDEPENDENT-SET. All you need to do is to add n isolated vertices to graph G (which is an instance of INDEPENDENT-SET and has n vertices). Let call this newly created graph G' (instance of CLIQUE-OR-INDEPENDENT-SET). Then it is not hard to prove...

algorithm,optimization,np-complete,np,bin-packing

There is a much better approach to solving the optimization problem based on the decision problem, note that your solution is exponential (pseudo-polynomial, but still exponential) in the size of the input, since if you have an algorithm that runs in T(n) on the decision problem, the suggested solution runs...

algorithm,graph,graph-algorithm,linear-programming,np-complete

It's possible to formulate this as the following problem. Suppose each vertex v in the graph has weight w(v). You define a variable x(v), and use some out-of-the-box linear programming solver to solve max \sum_v w(v) x(v) (maximize the weight of chosen vertices) subject to x(u) + x(v) <= 1,...

algorithm,np-complete,clique,vertex-cover

If there's two vertices from the clique not in a set, then the edge between them isn't covered, so any cover must have at least n-1 vertices. Any subset of n-1 vertices is a cover, trivially.