Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,715 questions
0
votes
1
answer
31
views
Is every discrete problem solvable in constant time for input within a given range of values?
Given arbitrarily large (but not infinite) memory is it possible to compute and store every possible output for every possible input beforehand thus making the program run in constant time?
- 101
0
votes
0
answers
35
views
Algorithmic complexity of computing ceil(log₂(n)) for arbitrarily large integers with bounded or no precomputation
I’m trying to understand the optimal complexity for computing ceil(log₂(n)) for arbitrarily large integers algorithmically.
Formally:
Let 1 ≤ n ≤ m.
I want to compute ceil(log₂(n)).
I’m allowed to do ...
0
votes
0
answers
12
views
Does the proof of Chaitin's incompleteness theorem assume that the programming language stores numbers in a base system>1?
Let's say we have a sentence in a formal theory $T$ of the form $K(n)>L$ where $L$ is the Kologmorov complexity of $n$ wrt some programming language.
Suppose numbers are written in the language in ...
- 101
1
vote
1
answer
58
views
Computing $\log(n)$ in logarithmic space
For a logspace-reduction, I am trying to prove that a logspace transducer can compute $\log(n)$ in base $2$ up to a precision of $\lceil\log(n)\rceil$ bits after the binary point, when the natural ...
- 13
1
vote
0
answers
41
views
Universal one-way function from Rule 110 cellular automaton?
Are you aware of any examples of universal one-way function construction using a cellular automaton (for instance Turing-complete Rule 110) or of any sufficiently strong cryptographic hash function ...
- 123
0
votes
0
answers
17
views
Complexity of determining whether a given probability distribution has maximal entropy
Let $W\neq\varnothing$ be a finite set of states and $\partial:W\rightarrow[0,1]$ a (rational) probability distribution on it. The size of $\partial$ is the number of non-zero terms in it. E.g., for $...
0
votes
0
answers
40
views
Which types of outputs are more likely to be produced by simple rule-based programs with fixed rules?
I’m interested in knowing how the complexity of outputs relates to the programs that generate them. For example, in cellular automata like Conway’s Game of Life (a grid-based system where simple rules ...
- 213
1
vote
1
answer
42
views
What's an example of a problem that is in Psearch, but not in NPsearch?
I was told during a lecture that there exist computational problems that are within $\text{P}_\text{search}$ but are not in $\text{NP}_\text{search}$ this seems impossible to me because I feel like a ...
- 11
0
votes
1
answer
46
views
derivation of $\mathsf{coNL} = \mathsf{NL}$ from $\overline{\mathtt{PATH}} \in \mathsf{NL}$ (Immerman-Szelepscényi theorem)
In Arora and Barak's book "Computational Complexity: A Modern Approach" (see draft pdf here https://theory.cs.princeton.edu/complexity/book.pdf), the $\mathtt{PATH}$ problem is given as the ...
0
votes
1
answer
75
views
Definition of search-NP and search-P
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
- 97
2
votes
1
answer
412
views
Understand the Levin reduction
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)~ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
- 97
5
votes
2
answers
163
views
How is $\overline{SAT}$ not obviously in NP?
First of all, I do know that it is not known whether or not $\overline{SAT}$ is in NP. But to me, it clearly looks like it is in NP. Given a Boolean formula φ with n variables, we nondeterministically ...
- 91
2
votes
1
answer
99
views
Proving NPhardness of linkedin queens
Consider the linkedin queens problem - our queens move like a rook + king on a nxn chessboard with coloured regions. The goal of the game is to place exactly queen in every row, column and coloured ...
- 21
1
vote
1
answer
186
views
Polynomial hierarchy, many-one reduction, but with co-NP subroutine
Let's say I have three problems, problem A is $\Sigma_{2}^{P}$-complete, problem B is co-NP-complete and problem C $\in \Sigma_{2}^{P}$.
In a many-one reduction from A to C (i.e. showing hardness for ...
- 13
1
vote
0
answers
24
views
Hypergraph partitioning constrained on partition size
I have a $k-$uniform hypergraph $H=(V,E)$ with $n$ vertices. I need to partition $H$ into two partitions of sizes $r$ and $n-r$. Is there an approximating algorithm that can do this while minimizing ...
- 111