# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

622 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
2k views

### Longest Repeated (Scattered) Subsequence in a String

Informal Problem Statement: Given a string, e.g. $ACCABBAB$, we want to colour some letters red and some letters blue (and some not at all), such that reading only the red letters from left to right ...
469 views

### Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
538 views

139 views

### Weakest reduction for P-completeness

It is common to define $P$-completeness with respect to logspace many-one reductions. I am looking for a complexity class $C$ such that if $C=P$ then all problems in $P$ are $P$-complete under many-...
128 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 ...
113 views

### Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is there ...
160 views

### On the Turing Completeness of First Order Logic

It is well known that in Descriptive Complexity Theory FO is equivalent to AC0. However, this accepts a couple of a theory and a string <T,s> iff the ...
84 views

### Complexity of Set Optimization with Sum of Rational Functions Objective

I encountered the following optimization problem. Let $S = \lbrace 1, 2, \ldots, n \rbrace$ be a set of items. Each item $i \in S$ has a non-negative benefit $b_i \in \mathbb R^+$, non-negative ...
87 views

### Decomposition of graphs that uses centers

Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
49 views

### Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
181 views

### P vs. NP and Godel's Theorems

This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct. Basically, I'm wondering if it is plausible for there to be a formal proof ...
148 views

### Can all types of problems be converted to decision problems?

We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is ...
257 views

### Reduce factoring to solving quadratic equations

The problem of solving quadratic equations is as follows: Suppose you are given a set of quadratic equations and are asked to find $0$-$1$ values for the variables such that all equations are ...
44 views

### Misunderstanding SS22 Sequencing to Minimize Tardy Tasks

I was reading "COMPUTERS AND INTRACTABILITY. A Guide to the Theory of NP-Completeness", and I am stuck at this part (page 236, SS22): In the second paragraph, 3rd line, the authors said that: "The ...
203 views

### propositional Modal logic filtration definition

Hello I have a slightly unusual question which relates to a definition of filtration structure. The following is my current state of the definition: $\mathcal{M} = (W, R, L)$, W is a set of worlds, ...
2k views

### Time Complexity of a Knapsack-derived problem

Consider the following problem: Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a ...