Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

3
votes
0answers
190 views

What is consequence of $PH\subseteq NSPACE((\log n)^2)$?

What is consequences of $PH\subseteq NSPACE((\log n)^2)$? We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
6
votes
1answer
116 views

Average-case analogue of Small-bias Spaces

Recall that an $\epsilon$-biased space is a set $S \subset \{0,1\}^n$ such that for every non-zero linear test $\alpha \in \{0,1\}^n \setminus \{0\}^n$, the expected bias $$| \mathbb{E}_{x \in S} [ (-...
5
votes
1answer
135 views

What does “hold uniformly” mean in the context of asymptotic analysis?

What does "hold uniformly" mean in the statement of Theorem 1.7 in A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):
3
votes
0answers
84 views

Critical Assignments vs Read-Once Branching Programs - Reference Request

Straight to the point: I'm looking for a reference for the fact that the complexity of a read-once branching program solving the search problem for an unsatisfiable formula $F$ is at least the ...
7
votes
0answers
187 views

Are there any known functions in NC2 but not in TC1?

Uniform TC1 is known to be in Catalytic Logspace. To improve the lower bound, we are looking for some functions known to be in NC2 but not in TC1. Also, what are some of the natural functions known ...
8
votes
1answer
280 views

Nondeterminism is on average useless for circuits?

Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result. Theorem[SW98]: For every constant $k>1$, almost all boolean functions with ...
1
vote
0answers
91 views

An explicit hard function for P/poly

It is known that $\textbf{MA}_{\textbf{EXP}} \not\subset \textbf{P/poly}$. Is it known any explicit language from $\textbf{MA}_{\textbf{EXP}}$ that does not belongs to $\textbf{P/poly}$? (An example ...
-1
votes
1answer
61 views

How to make any graph 2-degenerate?

I have to show a PPT(polynomial time reduction) from 'Colorful graph Motif' to '2-Degenerate Steiner Tree'. As input graph should be 2-degenerate, but here is normal graph G (that is, basically an ...
0
votes
0answers
49 views

Complexity of extending $P_4 $-partition of cubic graphs

This is a question I posted on MathOverflow before but never got an answer. I am cross-posting it here. Surprising phenomena occurs when we want to extend a partial solution of some easy problems. We ...
6
votes
1answer
239 views

What are the consequences of solving XOR 3-SAT in Logspace?

XOR Formulas Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
10
votes
0answers
236 views

Have people looked for parameterized algorithms for problems that are not in NP?

Are there problems that are not in NP (e.g., NEXP-complete problems) but admit FPT algorithms for a reasonable parameterization (and specifically, the standard parameterization of a problem -- the ...
9
votes
0answers
216 views

How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?

A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
-1
votes
1answer
74 views

Finding upper and lower bounds of a problem [closed]

We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans ...
1
vote
0answers
92 views

Proof of SAT is complete for NP via first-order reductions

So I have been reading this: https://people.cs.umass.edu/~immerman/book/ch7.pdf I do not understand the proof of theorem 7.16, which says that SAT is complete for NP via first-order reductions. My ...
2
votes
1answer
520 views

What is best known space requrement for solving SATISFIABILITY problem in exp time

I searched a lot for finding best space requirement algorithm for SATISFIABILITY problem but I didn't find any thing better than brute force that is in DSPACE(n). is there exists better bound? and ...
2
votes
0answers
42 views

Arithmetic circuits with restrictions on occurrence of pairs of variables

I am curious if the following model was studied or has some obvious lower bounds: We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going ...
2
votes
3answers
99 views

Reference request: Arithmetic circuit complexity

I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
2
votes
1answer
111 views

What is the best approximation and exact algorithm for vertex cover on cubic graphs?

"Best" = best performing in terms of run-time for exact algorithm and approximation ratio for an approximation algorithm.
1
vote
0answers
327 views

BQNC and Abelian Hidden Subgroup Problem

We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous. Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$? In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
2
votes
0answers
190 views

Primality in $NC$ hierarchy?

AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following: Input: integer n > 1. Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
0
votes
1answer
94 views

Is Prime Bounded Quadratic Congruence NP-complete?

Bounded Quadratic Congruence: Instance: Three positive integers $a$, $b$ and $c$. Question: Is there a positive integer $x<c$ such that $x^{2} \equiv a \, (mod \ b)$? Bounded Quadratic ...
1
vote
0answers
54 views

An alternative characterization of some NExp-Time Turing machine with oracles

Let me denote by $\Sigma_i^P$ be a class from i-th level of polynomial time hierarchy (see eg. PH). I'm interested in the following type of a Turing Machine $\mathcal{M}$: $\mathcal{M}$ is ...
5
votes
0answers
138 views

How hard is it to generate a set of relatively prime numbers between two given bounds?

Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
-1
votes
1answer
51 views

NP-Complete graph problems where a special vertex is given as input?

I am currently working on a graph theory problem where the instance includes a graph and a special vertex in the graph. I am trying to prove the NP-completeness of the problem as well as explore ...
0
votes
0answers
108 views

What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
3
votes
1answer
50 views

Complexity of distributively verifying that the diameter is small

Consider a graph $G=(V,E)$ and an integer parameter $k$. I'm interested in the round complexity, in the CONGEST model, of checking if the diameter of the graph is "much larger" or "much smaller" than ...
5
votes
2answers
101 views

A stronger multiplexing rule for soft linear logic?

In (intuitionistic) linear logic the usual rules for the storage modality $!$ are promotion, dereliction, contraction, and weakening: $$\frac{!\Gamma\vdash A}{!\Gamma\vdash !A}(prom) \qquad \frac{\...
4
votes
0answers
76 views

Circuits computing functions of inputs smaller than $n$

The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the ...
1
vote
0answers
145 views

Is there any NC-complete problem with respect to logspace reduction?

The question is on the title. We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
8
votes
1answer
93 views

$BPL$ with polylog random bits is in $L$

Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$. My question is ...
4
votes
0answers
71 views

2-hop distributed coloring in the CONGEST model

Consider a graph $G=(V,E)$ and let $d(u,v)$ denote the distance between $u$ and $v$ in $G$. A 2-hop coloring is a mapping $c:V\to{1,\ldots, C}$ ($C$ is the number of colors) such that $d(u,v)\le 2 \...
2
votes
1answer
127 views

Best $\Pi_k \text{SAT}$ running time?

Define $\Pi_k \text{SAT}$ by 'Given a quantified boolean formula $\varphi = \forall y_1\exists y_2\dots Q_ky_k\mbox{ }\phi(y_1, \dots, y_k)$, where $\phi(y_1, \dots, y_k)$ is boolean predicate with ...
1
vote
1answer
103 views

Can MONOTONE WSAT be in solved in polynomial time?

In the weighted monotone satisfiability problem (MONOTONE WSAT), the input is an n-variable MONOTONE CNF Boolean formula (when there is no a clause with a negated variable) and an integer k, and the ...
2
votes
0answers
217 views

Career advice needed: Switching from theoretical CS to pure math

I couldn't think of a better forum to ask this question. I am a first year cs graduate student. I couldn't really pursue theoretical cs during my undergrad, but as part of our PhD qualifiers, i had to ...
3
votes
0answers
193 views

Implications of resolving $BPP$ vs $PSPACE$

The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many ...
3
votes
0answers
128 views

Problems complete for non-deterministic PSPACE

We know that PSPACE = NPSPACE by savitch's theorem , but before that was proved , what problems were known to be complete for NPSPACE ?
6
votes
1answer
105 views

NP completeness of classes of spanning trees

I am teaching a complexity course, and I want to give some examples of similar looking problems such that one is in P, and the other is NP complete. This made me think of the following problem: does ...
3
votes
1answer
98 views

Relation between different “complexity theories” and complex systems theory

I know of at least 4 fundamentally different uses of the term "complexity theory": the study of how hard a problem is to solve using some sort of computing machine (I am ignoring divisions within ...
-3
votes
1answer
65 views

Is $P^{SAT} \subseteq NP$? [closed]

Is this known? Trivially, $NP \subseteq P^{SAT}$ as any problem in $NP$ is poly-time reducible to $SAT$. I am not quite sure about the other direction especially because the $NP$ machine would require ...
21
votes
4answers
818 views

Problems that are counter-intuitively solvable in practice?

Recently, I went through the painful fun experience of informally explaining the concept of computational complexity to a young talented self-taught programmer, who never took a formal course in ...
3
votes
0answers
128 views

What are the consequences if $W[i]=W[i-1]$?

$FPT=W[1]$ does not collapse the $W$ hierarchy however falsifies $ETH$ belief. Is there non-trivial consequence if $W[i]=W[i-1]$ and any other consequence at $W[1]$?
1
vote
0answers
108 views

Proof of Sipser-Lautmann Theorem

I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
4
votes
1answer
185 views

How hard is it to determine the chromatic number of a unit distance graph?

For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?
1
vote
0answers
95 views

Best way to represent NP-Hardness result for decision problem with two decision parameters

What is the best way to represent a NP-Hardness result for a decision problem with two decision parameters? Suppose we have a problem $P$ which asks to minimize two parameters $x$ and $y$ and we show ...
1
vote
0answers
75 views

What is the motivation behind W[P]?

I've been researching Parameterized Complexity Theory, and I've been puzzled by the definition of W[P]. Why is the number of non-deterministic steps bounded by $log|n|$? What is the intuition I should ...
9
votes
0answers
178 views

Regular expressions of prefixes/suffixes

It is well-known that star-free regular expressions, which are defined by the grammar $r::= a \mid r \cdot r \mid r \cup r \mid \neg r \mid \varepsilon \mid \emptyset$ where $a$ belongs to a finite ...
1
vote
0answers
37 views

Monotone complexity of PLP

Blum and Nisan show Positive Linear Programming could be done in $NC$ if we only ask for approximate solutions. This paper https://pdfs.semanticscholar.org/8dc7/5aa9d72864022d848c3e599c5f24d9d527e7....
3
votes
0answers
119 views

Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$? [closed]

We got an argument that 3-coloring bounded degree graphs is subexponential with complexity $O(\exp{(\sqrt{n}\log^2{n})})$. The treewidth of a planar graphs on $n$ vertices is $O(\sqrt{n})$ and 3-...
3
votes
1answer
123 views

On complexity of linear programming with quadratic equality/inequality constraints?

Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
6
votes
1answer
177 views

0-partition number vs partition number

Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all ...