Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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/...
user avatar
-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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
-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}...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 $ ...
user avatar
  • 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 ...
user avatar
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))$...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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\...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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}$ ...
user avatar
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 $...
user avatar
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 = \{\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
0 votes
0 answers
22 views

Peterson's leader election complexity

Giving the Peterson's algorithm for leader election in bidirectional ring: ...
user avatar
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$-$...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
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 $...
user avatar
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)$. • ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 - ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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}...
user avatar
  • 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)}$ ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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!
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

1
2 3 4 5
98