Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
85