# Questions tagged [reductions]

A reduction is the transformation of one problem into another problem. A example of using a reduction would be to be to show if a problem P is undecidable. This would be achieved by transforming or performing a reduction of a decision problem $P$ into an undecidable problem. If this can be achieved then we have shown that this problem P is undecidable.

199 questions
Filter by
Sorted by
Tagged with
139 views

### Are there complexity teaching resources that do not treat NP-hardness gadgets as Voodoo magic?

I am teaching a mini-complexity course to high achieving high-school students from my country this fall, and they have all expressed strong interest in learning more about what $P, NP$, reductions, ...
71 views

### Is universal hashing fully black-box reducible to error correcting code?

Fully black-box reduction is defined as in Notions of reducibility between crytpographic primitives, O. Reingold et al. Error-correcting code is used in the black-box abstract way in the sense that ...
1 vote
71 views

90 views

### Does GHC use graph reduction?

I have read somewhere that GHC does not use graph reduction for compiling/evaluating expressions. Is this right? If yes, what does it use as an alternative?
72 views

### On the Reductions of Functional complexity Classes

In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows: Function problem A reduces to ...
39 views

### Statements equivalent to strongly polynomial time linear programming

Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples: "linear feasibility solving is SPT" (due to ...
1 vote
52 views

### Reduction from unweighted graphs to weighted graphs?

Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around). My objective is to do something similar to the following: If the ...
60 views

### Existence of W-Hard construction from multiple hard problems

I am a research scholar working on parameterized complexity. Currently, I am exploring ways to prove the hardness of a problem by providing W-Hard constructions. A problem is known to be fixed-...
307 views

### Unclear proof step in Feder and Greene's 1988 paper showing NP-Hardness of approximating k-center problem within a factor of 1.82

I was reading the paper "Optimal Algorithms for Approximate Clustering", Feder and Greene  (https://dl.acm.org/doi/10.1145/62212.62255). Specifically, I was trying to look at the $1.82$...
1 vote
54 views

### What is region construction in timed automata?

I've recently started self-learning timed automata. There's this theorem in there that a timed automaton can be converted to a DFA using a "region" construction. I've looked up references on ...
119 views

1 vote
113 views

### A reduction from the maximum $k$-closure problem to the clique problem

Fix a partially ordered set $(P, \le)$ with $N$ elements and real weights $w(p)$ for each $p \in P$. A subset $S \subset P$ is called closed if for any $x, y$ with $y \in S$ and $x \le y$ we also ...
1 vote
230 views

### Can this NP-hardness proof for Super Mario Brothers (and other games) be simplified?

In "Classic Nintendo Games are (Computationally) Hard", a generalized framework based on reducibility of 3-SAT for proving NP-hardness of classic Nintendo games is presented, and several ...
168 views

### complexity class of a function - linear combinations and reductions (Fermionant, immanant, $GL_n$ representations)

The fermionant is a matrix function from physics, which is indexed by a positive integer $k$: \begin{align} \operatorname{Ferm}_k(A) = \sum_{\lambda} d_{\lambda}^{(k)} \operatorname{Imm}_{\lambda^T}(A)...
565 views

1 vote
70 views

### Some examples of tools to demonstrate problem is in $NC$ [closed]

Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
187 views

### 3-partition problem without the restriction to triplets

In the standard 3-partition problem, there are $3 m$ integers, their sum is $m T$, and they have to be partitioned into $m$ subsets of sum $T$ and size $3$. Consider the variant without the ...
232 views

### Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$. For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
1 vote
93 views

### Can a NEXP machine simulate invalid queries to a promise problem oracle?

Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output ...
663 views

### Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?

In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
1 vote
440 views

### Is the knapsack variant with small profit and unlimited repetition of items NP-hard?

Consider the unbounded Knapsack problem where we are given $n$ items of integral weights $w_i$, integral profits $p_i$, and a max weight $W$. The goal is to maximize the total profit $\sum_i x_ip_i$ ...
325 views

### Existing implementation of Scott's reduction?

As per this paper by Grädel, Kolaitis and Moshe Vardi, they discuss computational complexity of satisfiability problem in $\mathrm{FO^2}$, In order to do this they use Scott's reduction. Which is the ...