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

learn more… | top users | synonyms

3
votes
2answers
36 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\}$ ...
0
votes
1answer
28 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
36 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 ...
-1
votes
0answers
16 views

Running time of algorithms [closed]

Suppose for all integers $0 ≤ m$, $n < N$, Algorithms $A$, $B$, and $C$ compute the following: Algorithm $A$ computes $n + m$ in time $O(A(N))$ Algorithm $B$ computes $m · n$ in time ...
-1
votes
0answers
24 views

Polynominal Reduction [duplicate]

Given two NP-Complete Problems, there exists a polynominal time reduction from A -> B. Consider: The first problem $$ a^Tx = b, x \geq 0, x \mbox{ integer} $$ The second problem $$ Ax = b, x \geq 0, ...
3
votes
1answer
24 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 ...
0
votes
0answers
47 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
81 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
70 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
39 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 ...
1
vote
0answers
35 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
57 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
100 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
66 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
47 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
38 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
10 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, ...
2
votes
2answers
21 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
17 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
23 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
28 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
54 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
339 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
27 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
29 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
29 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
84 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
47 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
55 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
2answers
58 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) ...
3
votes
3answers
326 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
39 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
215 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
26 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
93 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
30 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
40 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 ...
1
vote
3answers
64 views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
1
vote
1answer
144 views

Reducing context-free languages with polynomial-time reductions

So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\{0^n1^n: n\geq 0\}$. Can $L \le_p M$ ? Why or why not? How do polynomial time reductions ...
4
votes
1answer
32 views

3 dimensionnal matching to partition transformation

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set ...
0
votes
1answer
35 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
2
votes
1answer
48 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
3
votes
1answer
35 views

Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
0
votes
0answers
33 views

Request for help with two reductions

Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other. Given a subset of a graph one needs to decide if the induced subgraph is triangle free. Can someone ...
-1
votes
1answer
53 views

Prove NP Complete

There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete? Solution: I can prove that it ...
1
vote
1answer
65 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
1answer
24 views

Example of reduction such that it is not many-one reduction while it is not turing reduction

I am reviewing things I learned, and I can't suddenly come up with an example of reduction that is not many-one, but Turing reduction. Can anyone present such an example?
0
votes
3answers
72 views

Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes. I want to show that this problem is NP-hard. Is there any ...
5
votes
0answers
66 views

NP-hardness of a special traveling salesman problem

Consider we have $n$ vertices, $v_1,\ldots,v_n$. We have two positive values $(a_i,b_i)$ associated with each $v_i$. The edge weight $w(v_iv_j)=a_ia_j+b_ib_j$. Is it NP-hard to solve the traveling ...