# Questions tagged [reductions]

In computability and complexity, finding mappings between problems that allow solving one problem using a solution of another one. For reduction in programming language theory (e.g. beta-reduction), see [lambda-calculus] or [term-rewriting].

1,080 questions
Filter by
Sorted by
Tagged with
257 views

706 views

### Is this problem NP-Complete (Bin packing with seperable items and penalty)?

The problem is a bit like bin-packing, so I'll describe it with similar naming: You have $N$ bins, with the same size, $V$, where $V$ is a positive integer This problem has items, and also "pieces" ...
36 views

### Shortening the number of reductions to prove NP-Completeness

This question is based on the slides from this pdf: Slide 54, they define the Subset Sum Problem. Slide 65, they define the Partition problem. Slide 74, they talk about the Job Scheduling problem. ...
81 views

### NP-Completeness and commutative property

If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$? My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.
49 views

186 views

### Is this a valid proof for “Karp-polynomial reduction is not symmetric”?

Let $L = \emptyset$ and $L' = \{a\}$ be two languages over an arbitrary non-empty alphabet $\Sigma$, $a \in \Sigma$. $L$ can be reduced to $L'$: the reduction just transforms anything it is given ...
5k views

### If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku. Can you treat this program as a black box and use this to solve ...
127 views

### A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
37 views

### Cluster with categorical / ordinal

i have a dataset with movies review. I wish cluster my element but inside i have a categorical / ordinal values. i seen that exist: MCA (Multiple Correspondence Analysis) https://www.utdallas.edu/~...
969 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
893 views

### Prove PSPACE is closed under union?

How would you prove PSPACE is closed under union? So far, my thought process is that we can create an algorithm to show that P is closed under union. I'm struggling with how I can connect that to ...
1k views

### Prove PSPACE is closed under complement? [duplicate]

How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect ...
46 views

### Exponential amount of information in polynomial size? Impossible!

I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183: Formula $F$ has a highly regular structure. It has $|x|$ ...
212 views

212 views

### Is maximum edge-weighted triangle-free graph NP-hard?

Given a graph $G$ with weights $w_e$ on the edges, choose a subset $S$ of the ''edges'' such that $S$ doesn't contain any 3-cycles, maximizing $\sum_{e\in S} w_e$. Is this problem NP-hard? I thought ...
54 views

### Finding a suitable NP-complete problem for reduction

We are given a set of names and a set of papers with names written on each side of the paper (not necessarily different ones and either side of the paper can be empty). Can we place the sheets on a ...
212 views

### Is this partitioning problem NP-complete?

I have a sequence of points $(x_1, \ldots, x_n)$ and a function $f$ that maps every consecutive subsequence (ie. of the form $(x_i, x_{i+1}, \ldots, x_j)$) to a real number. I want to split this ...
Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ ...