Questions about finding mappings between problems that allow solving one problem using a solution of another one.

learn more… | top users | synonyms

2
votes
1answer
46 views

Cycles in hardness of ST-CON for the class NL

It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete. I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction ...
3
votes
0answers
37 views

smallest satisfiability-equivalent formulas (generalized Tseitin transform)?

What is known about the following optimization problem for formulas in propositional logic: input: formula $F$ output: formula $G$ in CNF with $\mathrm{Var}(G) \supseteq \mathrm{Var}(F)$ such that ...
-2
votes
1answer
47 views

If an NP problem reduces to an NPC problem, it is NPC?

Is the following statement true? If a problem P1 is in NP and polynomial time reducible to P2, where P2 is NP-complete, then P1 is also NP-complete. Intuitively I think the answer is No because ...
0
votes
1answer
26 views

Reduction of Circuit Satisfiability to CNFSAT [duplicate]

CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce ...
2
votes
1answer
74 views

Reduce our problem to a known np-complete problem

Subgraph isomorphism We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$. Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ? (i.e. is there a subset of vertices of $G_2, V \subseteq ...
1
vote
1answer
36 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for ...
2
votes
0answers
133 views

PSPACE completeness, with different kinds of reductions

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction. This class is known as PSPACE-complete. ...
5
votes
1answer
109 views

Reduction from Vertex Cover to Polygon Cover

Polygon Cover: Input: A set of points $P$, a set of polygons $S$ in a 2D plane, and a positive integer $k \in \mathbb{N}$. Output: True if and only if there exists a subset in $S$ of at most $k$ ...
-2
votes
1answer
43 views

Proof of Circuit-Sat to Nand-Sat polynomial time many–one reducibility

Given a gate called Nand with the following truth table: A | B | A Nand B ------------------ 0 | 0 | 1 0 | 1 | 1 1 | 0 | 1 1 | 1 | 0 We can ...
0
votes
1answer
52 views

Poly-time reduction: D and D Comp [duplicate]

Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function. I will ...
0
votes
0answers
30 views

Reducing a Knapsack-type problem to a known problem

The Quadratic Knapsack problem, introduced by Gallo, is an optimization problem in the following form: $max \sum_{i=1}^n{\sum_{j=1}^n{q_{ij}x_ix_j}}$ $s.t \sum_{i=1}^n{w_ix_i} \leq c$ $x \in \{0, ...
1
vote
1answer
85 views

P-Completeness and Reducibility

I am taking an algorithm analysis class and am stuck on one of my homework problems and would appreciate it if I could receive some guidance. The problem I'm stuck on is proving that the empty ...
0
votes
1answer
126 views

Proving a language is not Turing-recognizable by reduction

I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment. I need to prove a language L is not ...
3
votes
3answers
339 views

The relation between 2SAT and 3SAT

Show that proving 2SAT is not NP-Complete would prove that 3SAT is not in P. Or eqivalently - Show that proving 3SAT is in P would prove that 2SAT is NP-Complete. I can see there is an ...
3
votes
2answers
70 views

Restricted Integer Programming

The integer feasibility problem is NP-complete: $Ax=b, x \geq 0, x \mbox{ integer}$ $A$ contains elements in $\mathbb{R}$ If we restrict this: $A$ contains only elements in: $\{1,0\}$ ...
1
vote
2answers
57 views

If $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$

How to prove if $B$, $\overline{B}\neq \varnothing$ , then for every recursive set $A$, $A \leq_m B$ ? it means every recursive set is mapping reducible to set $B\neq \aleph$. I really have no idea ...
1
vote
2answers
49 views

Is it true, If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive?

If $A$ is turing recognizable and $A \leq_m\bar{A}$ then $A$ is recursive? If it is true how to prove it? Update It is my attempt, If $A$ is turing recognizable (r.e.) and $\bar{A}$ is r.e. then ...
3
votes
1answer
34 views

Methods of turning a decision problem into finding the certificate?

I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If ...
1
vote
0answers
87 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
2
votes
1answer
84 views

Reduction to $n\log n$ time problem

If a problem $A$ is poly-time reducible to a problem $B$ ($A <_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?
0
votes
1answer
119 views

Polynominal reduction from unbounded knapsack problem to general integer programming

Given an oracle that can solve in polynominal time: $$a^Tx=b$$ $$x \geq 0$$ So it can solve the feasibility problem with one equality-constraint(a is here a vector and b is a constant, x is required ...
2
votes
0answers
50 views

Ideas on reducing Traveling Salesman to Metric Traveling Salesman?

I want to show a polynomial reduction from TSP to Metric TSP. I know the rule is: $(G, k) \in TSP \iff (G', k') \in MTSP$ where $G$ is some graph, and $k$ is some bound. It seems like whatever I map ...
2
votes
1answer
44 views

Linear and almost-linear perfect hashing

I am trying to understand the sentence from a paper by Patrascu: Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity The ...
-1
votes
1answer
80 views

Let A,B be languages. If A is decidable and B undecidable, then A reducible to B

So I'm learning for an upcoming exam and there's a specific problem which I can't show: Let A be decidable and B undecidable, then $A \le B$ Can someone give me a hint how to solve that? ...
3
votes
3answers
200 views

4-color to 3-color polynomial reduction

I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ? I have been searching for the right way to make this reduction for a while now. I would love some ...
3
votes
1answer
139 views

Variants of the 3-SUM problem

The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there ...
2
votes
2answers
54 views

Logical Reduction

Reducing one computable problem to another by providing an algorithm which transforms an instance of one problem to one of the other (and limiting the time or space of that algorithm) is clear to me. ...
2
votes
0answers
48 views

What is the trick of “adding a huge number” for in the reduction from $\textsf{3-Partition}$?

Problem: To prove the $\textsf{NP-Completeness}$ of the problem of "Packing Squares (with different side length) into A Rectangle", $\textsf{3-Partition}$ is reduced to it, as shown in the following ...
0
votes
0answers
13 views

Solving $Isomorphism$ using $AUTOM$ in polynomial time

Let $Iso$ be the language of all $<G,H>$ such that $G$ and $H$ are isomorphic, and $AUTOM$ be the language of all $G$'s such that $G$ has a non-trivial automorphism. I'd like to show that, ...
3
votes
2answers
23 views

$3EQ \leq _P 2EQ$

Let: $2EQ$ - The language of all binary ($\mathbb{Z}_2$) equation sets that have a solution in $\mathbb{Z}_2$, where each multiplication is of at most two $x_i,\, x_j$. Meaning a set of equations of ...
2
votes
0answers
34 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
1
vote
1answer
32 views

Reduce Clique to Vertex Cover

I read on the internet that it's possible to reduce Clique to Vertex Cover. Almost everyone use this theorem: if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of ...
1
vote
1answer
34 views

SAT-3CNF - Clique [closed]

Could someone show me ( or give me a valuable hint) how to reduce k-Clique problem to SAT-3CNF problem ? I am able to prove reduction from SAT-3CNF to k-Clique, but in the opposite direction it's ...
2
votes
0answers
33 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
2
votes
1answer
56 views

Reduction from a further constrained problem

If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard? Generally, this is probably not the case. For ...
2
votes
1answer
366 views

Reducing a non-RE language to its complement

Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...
1
vote
1answer
31 views

Reductions where the number of certificates from one problem can be computed for another to varying degrees

Let $A$ and $B$ be two decision problems in $NP$. Consider three cases: (1) For any instance of problem $A$, one can produce, in polynomial time, an instance of problem $B$ having exactly the same ...
0
votes
1answer
33 views

Validity of reduction (3-SAT)

I'm trying to show that a special variant of the common 3-SAT is NP-complete by reducing 3-SAT to this special variant. This special variant works like the normal 3CNF-SAT, except every other clause ...
1
vote
1answer
31 views

Randomized and deterministic reduction

Given a problem $X$, to show it is is $\sf NP$-complete, one usually shows a deterministic reduction from an $\sf NP$-complete problem. If it is hard to show deterministic reduction, then one shows a ...
3
votes
1answer
139 views

Reducing Exact Cover to Subset Sum

Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete. Hint: Use ...
3
votes
1answer
54 views

Characterizing the range of a polytime function

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is ...
3
votes
2answers
67 views

Can someone provide a trivial example to the “reduction” procedure used to prove hardness? [duplicate]

I cannot comprehend how you can prove hardness between two NP complete problems. For example, let X be a NP hard problem, I want to prove Y is also NP hard. I can do this by reducing X to Y, if Y is ...
1
vote
3answers
113 views

Turing Machine That Accepts Machines With Undecidable Languages

So I'm reviewing my Computability notes for my final, and I understand how reduction arguments work, but I'm having trouble framing one for the following Turing machine: Undecidable TM = { ⟨M⟩ | L(M) ...
4
votes
3answers
406 views

Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), ...
1
vote
1answer
62 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if ...
5
votes
1answer
221 views

How a reduction can help up solve a problem?

I am studying the basics of Computation Theory and I came up with an example I can't understand. Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of ...
2
votes
0answers
28 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
-3
votes
1answer
96 views

Showing that M is NP-Complete

An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that each item in $T$ belongs to some $S_i$, and ...
0
votes
0answers
34 views

Is it decidable whether a TM accepts more than one word?

Is the following language: $\qquad\displaystyle L= \{\langle M\rangle \mid M \text{ is a TM }, |L(M)|>1\}$ Turing-decidable? I think it isn't, because if a Turing machine T can ...
0
votes
0answers
54 views

Reduction of specific scheduling problem to show np-completeness

Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k: Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...