# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

5,284 questions
Filter by
Sorted by
Tagged with
20 views

### Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds

Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system: 1: Assume that initially the nodes have IDs of size $\log(n)$ bits 2: The root is ...
• 305
1 vote
44 views

### Why do simple Logical Gates have an Irrational amount of Bits?

Suppose $2$ bits are used to encode a message, A and B. If you know $A$ is $1$, you have one bit of information. If you know $A\land B$ is $1$, you have two bits of information. If you know $A\land B$...
• 13
32 views

### On proving the uncomputability of Kolmogorov complexity by contradiction

I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry ...
• 163
282 views

### Constructing equivalent (to a polynomial-time degree) decision problems from function problems

Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$. Now, we're given some language, $L \subseteq \Sigma^*$ ...
• 265
1 vote
76 views

### Integrality gap and complexity classes

I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems? In particular, is there a class of problems for which their integrality ...
26 views

### is this lanuage or it' complement not Turing-recognisable

K = {<J, a, b, c> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}. ...
64 views

### Can you enumerate the set of all words over a finite alphabet?

Can you enumerate the set of all words over a finite alphabet?
60 views

### Can all NP-complete problems be reduced to NP?

I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around? Can all NP-Complete be reduced to NP problems? My understanding is ...
159 views

### Can protein folding destroy cryptography?

They say that protein folding is an NP-hard problem, meaning that if we could figure out how any protein folds, we could solve any NP problem in polynomial time. However, doesn't this basically ...
1 vote
38 views

### Lower Bound on Parity of Boolean Functions

Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
• 13
34 views

### If NP problems are decidable, and decidable is subset of turning recognizable which recognizer can understand them?

I think the best way to explain my question would be to have sextuple (regular, context-free, Turing-recognisable, decidable, P, NP).were you fill out 1 for promblem which lies into that section, ...
1 vote
25 views

### Can someone please explain classes MA and AM (with an example)? What happens to AM in case of PH[2]=PSPACE?

I am trying to understand two player (prover-Merlin and verifier-Arthur) interactive proof complexity classes and had a few doubts. As I understand, the classes $MA$ and $AM$ involve two players, ...
• 743
1k views

### What is the complexity of theorem proving?

I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
84 views

### If X is poly-time reducible to Y and X is in P, then Y is in P

The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
48 views

1 vote
22 views

### Class of optimization problems whose decision versions are in P

NPO is defined to be the class of optimization problems whose decision versions are in NP. I would like to get the complexity class of optimization problems whose decision versions are in P. Is such ...
39 views

### Hardness of the bin packing problem

I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that $$1 > a_1 \geq a_2 \geq \dots \geq a_n > 0$$ The ...
606 views

### Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?

You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
29 views

• 5,790
71 views

### Finding maximum via sum oracle

Let $A$ be an array of real numbers with a unique maximum element, such that $size(A)=O(2^N)$. Assume that we have an oracle that can evaluate a sum over any subset of indices of $A$ in $O(1)$ time. ...
• 133
75 views

### Understanding reductions and notation

I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
44 views

### Why are polynomials a natural measure for easiness of computational problems? [duplicate]

We understand the exponential function to constantly grow, which we consider bad for a problem. By constantly growing I mean the ratio $\frac{f(n+1)}{f(n)}$ never tends to 1, where $f(n)$ is the ...
22 views

If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
• 13
14 views

### Relativizations/Oracles for the BPP and RP complexity classes

If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
• 13
57 views

### Finding a Polynomial Time algorithm for the 3-SAT Problem

Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause : Ai = (xr $\lor$ xs $\lor$ xt) where 1 $\le$ r,s,t $\le$n and ...
194 views

### Is this path planning problem NP-complete?

Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then ...
14 views

### Analogue of NP for oracle problems

I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems. The ...
• 265
33 views

• 153
1 vote
### Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$
I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...