# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,207 questions
Filter by
Sorted by
Tagged with
19 views

### Complexity in time and memory for graph search algorithm

I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
18 views

### Finding a kernel for d-Bounded degree deletion

In $d$ Bounded degree deletion problem, we are given an undirected graph $G$ and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the the maximum ...
16 views

### 3-OCC-MAX SAT np-complete?

Assuming 3-OCC-MAX SAT is the language of all CNF formulas in which every variable appears in at most 3 clauses. Is this problem NP-Complete? I'm trying to find a karp reduction between SAT and this ...
59 views

### Proving a tighter upperbound (big-O) for this problem

Motivation So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: ...
28 views

### Is Partition Problem with non-integer input NP-complete?

The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$? I have read a lot of proofs using ...
48 views

### Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ...
40 views

### Sorting $n^2$ numbers which consist of numbers from 1 to $n$

I wish to sort $n^2$ numbers which all come from the set $\{1,2,3,...,n\}$, i.e duplications are allowed. I know I can just use merge sort which has complexity $\mathcal{O}(n^2\log (n))$, but I was ...
43 views

### Show that the OR of n variables cannot be expressed as a polynomial over Fp of degree less than n

Here is a question from Computational Complexity by Arora and Barak: Show that representing OR of $n$ variables $x_1,x_2,\dots,x_n$ exactly over a polynomial in $GF(q)$ requires degree exactly $n$. (...
29 views

### The following time complexity is right for the given algorirthm

Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct? ...
25 views

### Showing that carbon is not a complexity measure per Blum

In Computational Complexity by Papadimitriou, there is an exercise about Blum's axioms where it asks to prove that several measures for the complexity of a Turing machine satisfy them. 7.4.12 Blum ...
138 views

### Does O(1) communication complexity imply that a language is regular?

Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
36 views

### Examples of exponential time linear space exact algorithms

I am looking for examples of NP-complete problem-solving exact algorithms with a linear space complexity and an exponential time complexity. Algorithms which solve the k-SAT problem exactly (such as ...
72 views

### What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

I have seen the formulations there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time a problem requires time $n^{2-o(1)}$ a problem requires time $\Omega(n^2)$ being used ...
74 views

### A communication problem about graphs

An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A \dot\cup E_B = E$. Initially, ...
36 views

### Time complexity of the immanant

Let $A$ be an $n \times n$ matrix over some field $\mathbb{F}$. The determinant $$\det(A) = \sum_{\sigma \in S_n} \operatorname{sgn}(\sigma) A_{1 \sigma(1)} \cdots A_{n \sigma(n)}$$ can be evaluated ...
80 views

### Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?

This answer seems incorrect to me: Which NP-Complete problem has the fastest known algorithm? The fastest solution for one NP-Complete problem should be the fastest solution for all NP-Complete ...
26 views

### Bottleneck TSP with repeated nodes

I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
34 views

### Fastest way to determine constrained sum of an array

I have two $N$-vectors of positive integers, called cost and gain, and I have another integer called ...
86 views

### On the usage of Arora and Barak's main lemma in their proof of the PCP theorem [closed]

I am working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in the part titled &...
13 views

### Level Ancestor Query long-paths algorithm complexity of sqrt n

Can someone explain why the complexity of a query for LA is √n when we only decompose the tree into long-paths? How can we show/prove that? How can we prove that the number of paths can be as high as ...
34 views

### What is the smallest time/space complexity class for which no sparse language is hard?

For example, whether there exists $\mathsf{PSPACE}$-hard sparse language an open problem, as it is not yet known whether polynomial hierarchy collapses. But is it a solved problem for larger ...
39 views

### Schwartz-Zippel lemma question

Schwartz-Zippel lemma is as follows. Let $f(x_1,\ldots,x_n)$ be a polynomial of total degree at most $d$ over a field $\mathbb{F}$ and assume that $f$ is not identically zero. Pick uniformally at ...
24 views

### Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps ...
19 views

### Why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, $p$ and $q$ prime

I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, where $p$ and $q$ are distinct primes. ...
19 views

### How to prove the complexity of this modified version of the minimum dominating set problem?

I have an optimization problem and I want to show its complexity. The optimization problem is the same as the minimum dominating set problem, but with an additional constraint. The constraint is easy. ...
97 views

30 views

### Asymptotic Complexity Proofs

Let $f, g : \mathbb{N}\to\mathbb{R}$ be two real-valued functions greater than $1$. Consider the following two statements: (A) $f(n) = \Theta(g(n))$ (B) $\log f(n) \sim \log g(n)$ (a) Prove: (B) does ...
24 views

### Can you say anything interesting about a language knowing only that it is prefix-closed?

Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$). Knowing only ...
24 views

### Lowest complexity - Number closest to 0

I'm currently trying to improve my algorithm skills and I was trying a simple algorithm : Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his ...
67 views

### Hardness of maximizing difference of functions

Suppose that the problem of maximizing a real function $f$ over a certain domain $D$ is NP_HARD. What can be said about the problem of maximizing $f-g$, with $g$ being another function over $D$? Is it ...
18 views

### Computational complexity in Boolean network

An Boolean control networks can be expressed as \begin{equation} \label{ControlBN} \left\{\begin{array}{l}{x_{1}(t+1)=f_{1}\left(x_{1}(t), \cdots, x_{n}(t), u_{1}(t), \cdots, u_{m}(t)\right),} \\ {x_{...
28 views

### Why is it hard to show that the euclidean Steiner tree problem is in NP?

I read that for the euclidean Steiner tree problem it is known that it is NP-hard, but not known whether it is in NP or not. [Wikipedia] Shouldn't the euclidean version obviously be in NP since the ...
15 views

### What does a kernel of size n,n^2 ,… mean?

So according to Wikipedia, In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the ...
22 views

### Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}

I have the following question : \begin{align} L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\ \text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\} \end{...
31 views

### In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

In what cases is solving Binary Linear Program easy (i.e. P complexity)? The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
93 views

### Why Study Complexity Theory?

I’m an amateur in the study of algorithms. For a while I’ve had a burning question, why do we study complexity theory in computer science? The reason I ask is because algorithms with better ...
25 views

### P vs NP characterization confusion

I know that $P \subseteq NP$, but for a problem in $P$, e.g. MST in a graph, is it a correct statement to say that: The MST problem belongs in NP-Class. (I mean, i think it is correct, but could ...
I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?" Whether a graph is $k$-colorable ...