Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,884
questions
0
votes
1
answer
56
views
Does a constant time compression algorithm proves that P=NP?
Supposed someone came up with a compression algorithm that doesn't iterate through bytes or anything to compress data, does that proves P=NP?
That is, an algorithm that doesn't rely on patterns/...
-3
votes
0
answers
29
views
Fixed parameter tractability Big O
Was wondering if anyone had some guidance as to whether the following big-O expressions are fpt and what the smallest possible set of parameters would be to make them fpt.
- 1
0
votes
0
answers
50
views
Binary compression algorithm with decompress by index
I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
0
votes
2
answers
47
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
-1
votes
0
answers
21
views
How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions? [closed]
I want to calculate the computational complexity in term of the big ($\cal O$). My equation is:
It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}...
- 99
1
vote
1
answer
79
views
How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:
Imagine that the following big-O expressions ...
- 13
0
votes
0
answers
23
views
What kind of CNF and DNF are in P [closed]
could anyone help me to prove which languages are in P? I will present my thoughts but I do not know how to go from there. Thank for any help
l1 = {L | L is on CNF and is satisfiable}
l2 = {L | L is ...
- 103
1
vote
2
answers
48
views
Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?
If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata?
Bonus question: Can ...
- 11
1
vote
0
answers
21
views
Showing that $ASPACE(f (n)) = DTIME(2^{O(f (n))})$
My lecture notes for complexity says that $\mathsf{ASPACE}(f (n)) = \mathsf{DTIME}(2^{O(f (n))})$
I can prove the forward direction ($\mathsf{ASPACE}(f (n)) \subseteq \mathsf{DTIME}(2^{O(f (n))})$) by ...
- 331
3
votes
2
answers
287
views
Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2 return 1
3 else
4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)
I defined a recurrence
$ ...
- 45
1
vote
1
answer
44
views
What would $P = NP$ tell us about how the polynomial hierarchy relates to $PSPACE$
If $P = NP$ it's easy to show by induction that the $PH$ collapses to $P$. But would that have any other implications for the relation between $PSPACE$ and $PH$? We already know that $PH \subseteq ...
- 331
2
votes
2
answers
83
views
Exponential Time Hypothesis and the input size vs number of variables
According to Exponential Time Hypothesis there does not exist a deterministic algorithm to solve SAT over $V$ variables in time $o(2^V)$. However, let's say the number of literals $n = \omega(poly(V))$...
- 1,381
1
vote
1
answer
56
views
Time Complexity of Exponentiation Operation as per RAM Model of Computation
Now, $\color{blue}{\text{Exponentiation}}$ is defined as
Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and ...
- 219
1
vote
1
answer
43
views
Sum in counting satisfying assignments
Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of ...
- 11
1
vote
0
answers
17
views
Running time of 01-Knapsack-like with negative weight/values, absolute value weight constraint, and volume constraint?
Background
In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of $n$ items where item $i$ has weight $w_i\in\mathbb{N}$, volume $u_i\...
- 153
0
votes
0
answers
18
views
Where are some examples of unsatisfiable formulas? Especially about 3CNF paradigm
I've been learning co-NP recently. I know that UNSAT $\in$ co-NP. So I want to find more examples of UNSAT, especially about 3CNF paradigm.
- 141
3
votes
1
answer
190
views
Shannon's result that some Boolean functions require exponential circuits
In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
- 8,168
0
votes
0
answers
29
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 131
1
vote
0
answers
22
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
0
votes
0
answers
12
views
A simple clarification on polynomiality of sequential construction of Turing Machines through plus construction
Suppose our original $NDTM$ $M_0$ has $N<2^t$ number of acceptance paths. We construct $r$ different $NDTM$s $M_1,\dots,M_r$ with each with $m_1,m_2,\dots,m_r$ acceptance paths respectively where $...
- 17
1
vote
0
answers
23
views
pseudo dimension of the minimum of functions
Suppose a real-valued function class $\mathcal{F}$ with pseudo dimension less than $d$, I am wondering what is the pseudo dimension of the following function class
\begin{equation}
\mathcal{F}_2 = \{\...
- 111
0
votes
1
answer
16
views
Is $\frac{opt}{c}(1-\epsilon)$ for some constant c >0 considered a PTAS?
So I am studying PTAS algorithms. For a maximazation problem the difinition says that an algorithm that has value A , is a ptas if :
$A \geq opt(1-\epsilon) \; ,\forall \epsilon > 0$
(and I guess ...
- 191
1
vote
0
answers
41
views
A minor issue on the proof of "if (L',D') is easy, then so is (L,D)" in Average-case Complexity!
In Arora and Barak's textbook, in chapter 18, p.366-367, they prove the following theorem:
Theorem 18.7 if $(L,D)$ is reduced to $(L',D')$ and $(L',D') \in disP$, then $(L,D) \in disP$
The proof ...
- 707
0
votes
1
answer
25
views
Does FPT allow for doubling the parameter?
I have recently come across a result that showed that a given problem is in FPT when parameterized by the treewidth of a graph. However, they did this by showing that the problem is in FPT when ...
- 145
3
votes
1
answer
850
views
How does the 'proof' of the Cook-Levin theorem, actually prove the Cook-Levin theorem?
I was wondering if someone could help resolve some issues I have understanding the proof given for the Cook-Levin theorem provided in the Sipser text (3rd edition) – as this proof has truly stumped me....
- 51
1
vote
0
answers
17
views
Deterministic Algorithm for searching for object $d$ units down one road in a $k$ road intersection
Suppose we are at the centre of a $k$ road intersection (i.e, there are $k$ different roads radiating out from where we are standing, infinitely). Suppose along one of these roads is a treasure.
This ...
2
votes
1
answer
54
views
NP-completeness of some problems on assigning candidates to departments
Suppose we have $n$ candidates from a candidate pool $\{1,2, .., n\}$ and we have $m$ departments. A candidate can be assigned to at most one department (so not being assigned is possible). Each ...
- 21
2
votes
1
answer
34
views
Complexity of a restricted SAT problem
I am wondering about the complexity of the following SAT related problem:
Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties:
The intersection of any pair of ...
- 23
3
votes
1
answer
41
views
Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Suppose the optimal color assignment of graph $G$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $\overline{G}$?
A ...
- 170
0
votes
0
answers
22
views
Peterson's leader election complexity
Giving the Peterson's algorithm for leader election in bidirectional ring:
...
- 1
1
vote
1
answer
43
views
Proving the NP hardness of two variants of SAT
$k$-$\text{RSAT}$ is a variant of $k$-$\text{SAT}$ where we restrict our attention to formulae in
which each variable occurs at most $3$ times, and each literal occurs at most twice. The language
$k$-$...
- 331
1
vote
1
answer
39
views
Can we show that #3CNF is in FPTAS
If we have a deterministic algorithm $A$ such that $\#3CNF \in APX$, how can we show that there is a fully polynomial deterministic approximation scheme for $\#3CNF$? How can we show that $\#3CNF \in ...
- 33
-1
votes
0
answers
19
views
Proving that BeliefRevision is in APTime
We define the belief revision problem for propositional logic as follows. Let $F$ be
a set of propositional formulas and let $ϕ$ and $ψ$ be propositional formulas. Given propositional
interpretations (...
- 331
1
vote
1
answer
18
views
(Approximation) Algorithms for Weight Distribution / Subspace Weights Problem in coding theory [closed]
The Weight Distribution / Subspace Weights Problem in coding theory is defined as this:
Instance: A binary $m$ by$n$ matrix $H$ and an integer $k > 0$
Question: Is there a set of $k$ columns of $...
- 11
1
vote
1
answer
39
views
Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:
• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.
• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.
• ...
- 331
1
vote
1
answer
35
views
Complexity of Nelder-Mead Algorithms
If the objective function contains $n$ variables (e.g. $f(x_1, ..., x_n)$) in the Nelder-Mead algorithm (or other direct search methods), is there any known lower/upper bounds on how many times the ...
- 23
1
vote
1
answer
27
views
Proving 2SAT is in P vs algorithm for finding a satisfying assignment
I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path ...
- 113
1
vote
1
answer
19
views
Serializing Chess Games
This is an open question I have been thinking about lately. Let's say we are black player and we play two "harmless" moves A and B. We assume it won't change anything if we play A - B or B - ...
- 13
1
vote
0
answers
28
views
Prove that CorrectConnSolver is coNP-Complete
I need to prove that CorrectConnSolver is coNP-Complete where CorrectConnSolver is defind as follows:
CorrectConnSolve$= \{C | C(G) = 1 \iff G$ is connected$\}$.
In other words, the
...
- 23
1
vote
1
answer
40
views
prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$
I need to prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$.
Where CorrectSATSolver $= \{C | C(\varphi) = 1 \iff \varphi$ is satisfiable$\}$. In other words, CorrectSATSolver ...
- 23
0
votes
0
answers
26
views
Proving the load balancing problem is NP-Complete
The load balancing problem:
Given we have $m\ge3$ machines (servers) $M_{1}, M_{2},\dots,M_{m}$. As input we are given $n$ jobs defined by their processing times: $t_{1},t_{2},\dots,t_{n}\in\mathbb{Q}...
- 49
1
vote
1
answer
29
views
Comparing two functions rate of growth
This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question.
Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
- 187
2
votes
3
answers
83
views
Complexity of string comparison vs whitespace-trimmed string comparison
I recently worked on an algorithm which, among other things, checks strings for equality using the classic builtin equality operator:
str1 == str2
(I think it ...
- 73
2
votes
1
answer
20
views
Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$
Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the ...
- 170
1
vote
0
answers
17
views
Why results based on padding generally fail to relativize?
I have read in the Algebrization paper that, if we only allow polynomially-long queries to oracles, then, results based on padding will not relativize. For instance: assuming that $A$ is a PSPACE-...
- 307
2
votes
1
answer
21
views
First-order model checking is not fixed parameter tractable on general graphs
I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs.
Why is this the case? Would be happy about some reference
Thanks in advance!
- 35
1
vote
1
answer
28
views
A Question in Arora & Barak's Book: $577 \times 423$
I have been reading [1] recently. On page xxi, the authors wrote: "For example, multiplying 577 by 423 using repeated addition requires 422 additions, whereas doing it with the grade-school ...
- 305
0
votes
0
answers
20
views
Does the assertion that most Boolean functions require exponential-sized circuits implies that most languages are at least NP?
The one thing we do know is that almost all Boolean functions require
exponential-sized circuits. (Computational Complexity: A Modern Approach)
If a language A ∈ TIME(t(n)), then A has circuit ...
- 287
2
votes
0
answers
14
views
Understanding a black-box vs white-box simulation and relativization
I am trying to understand the relativization barrier from Baker Gill Solovay (BGS).
About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
- 307
0
votes
0
answers
43
views
Efficiently finding range from ordered list of ranges with preprocessing
Say we have a list of ranges like so:
ranges = [(0, 100), (101, 200), (201, 300)]
The ranges will always be ordered, never overlap, and perfectly align.
We want to ...
