Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,207
questions
1
vote
0answers
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....
1
vote
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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: ...
0
votes
0answers
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
2answers
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$.
(...
0
votes
0answers
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?
...
1
vote
1answer
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 ...
4
votes
2answers
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 ...
2
votes
0answers
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 ...
4
votes
3answers
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 ...
2
votes
0answers
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, ...
3
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
5
votes
0answers
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 &...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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. ...
0
votes
0answers
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. ...
0
votes
1answer
97 views
3SAT to 3SAT-WITH-MAJORITY reduction
I've been struggling with reduction while solving this exercise and I would really appreciate some help if not the solution.
Problem: [3-SAT-WITH-MAJORITY]
Input: A set of clauses $C = {\{c_1, \dots, ...
3
votes
1answer
54 views
Self study materials for computational complexity theory
I will be taking a computational complexity theory course in about a year, and as the reference material will be Computational Complexity A Modern Approach I am more than confident that without a ...
0
votes
0answers
19 views
Expected runtime for hashing with a binary search tree as collision handling
I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
1answer
27 views
Is it a sufficient condition to be in NP?
Suppose the following situation.
You have a decision problem $D$.
You know that $SAT$ is $NP$-complete.
You know that $D\leq_p SAT$.
Can you conclude that $D\in NP$?
I think it's true because it ...
2
votes
1answer
24 views
Leader Election: Every bit-reversal ring is $\frac{1}{2}$-symmetric
I have a proof that I need help with. Like the title says, the theorem is that every bit-reversal ring is $\frac{1}{2}$-symmetric. The theorem is for Leader Election algorithm in synchronous ring. The ...
-1
votes
0answers
26 views
mathematical formulation complexity
How to find the complexity of a mathematical formulation ( in terms of constraints and variables)
(We refer generally to the notation (o(n^2) variables and o(n^3) constraints)
( I would be grateful if ...
3
votes
1answer
441 views
Why does the time hierarchy theorem use a rather intricate diagonal argument?
Isn't it possible to prove it by defining some problem that can be solved in $f(n)^2$ in the worst case due to its output always being $f(n)^2$ characters so that it won't be solvable in $f(n)$?
Where ...
0
votes
3answers
61 views
If a function $f(n)=\Theta(g(n))$, does it follow that $f(n/k)=\Theta(g(n))$ for a constant $k$?
Suppose the following is true for some f(n) and g(n):
$f(n) = \Theta(g(n))$
Does that mean $f(n/k) = \Theta(g(n))$ for any value of $k>0$?
I know that for the above to be true, there must exist ...
3
votes
2answers
42 views
Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts
From Nielsen & Chuang (page 138):
Suppose an $n$ element list is sorted by applying some sequence of
compare-and-swap operations to the list. There are $n!$ possible initial
orderings of the list....
0
votes
1answer
42 views
3SAT and directed graph
Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
1
vote
7answers
3k views
Why can't we say that a Neural Network is a NP problem solver?
From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The ...
2
votes
2answers
36 views
Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\lg_b^{a+\epsilon}})$
I know that the regularity condition for master theorem Case#3 stating that [$af(\frac{n}{b}) ā¤ cf(n)$ for some constant $c < 1$ and all sufficiently large n] always holds when the $f(n)=n^k$,$f(n)=...
-2
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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_{...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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{...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
10 views
Is a graph at least k-colorable? (Complexity)
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 ...
0
votes
1answer
20 views
Complexity of “does a directed graph have <=1 Hamiltonian cycles?”
I am studying the complexity classes and I am confused what is the complexity of the following problem: "Does a directed graph G has at most 1 Hamiltonian cycle?"
So, from my knowledge and ...
