Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

1
vote
0answers
49 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
134 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 ...
1
vote
0answers
98 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
47 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
92 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
74 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
113 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
89 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
64 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
122 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
93 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
200 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
163 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
125 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
99 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
92 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
62 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
787 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
120 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
100 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
175 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
94 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 ...
0
votes
0answers
63 views

Algorithm for solving majority of a group of k hidden elements

You may already be familiar with algorithms to compute the majority using multiple queries. The way these problems work is that you are given a bin of $n$ marbles of binary colors, whose colors you ...
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
176 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
36 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
111 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-...
0
votes
0answers
28 views

Complexity assumptions and practical protocols

What are necessary and sufficient conditions for some form of public-key infrastructure to be possible? SSH? TLS? Kerberos? Symmetric encryption? What about in the post-quantum world?
3
votes
1answer
121 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
172 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 ...
3
votes
0answers
133 views

Formalization of proofs and CC paradox? - Part II

This was the second part of my previous question. It is very similar, and probably it has a similar answer (as Emil said in a comment), but I thought it was worth to separate it and ask it as a new ...
6
votes
1answer
131 views

Path in a graph with durations [closed]

I have the following problem: given a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\...
0
votes
0answers
42 views

Memory failure computation

Is there any research into models of computations with failures? For example, a Turing machine tape that stores the correct value with a certain probability? Or the cell has a certain probability of a ...
0
votes
0answers
49 views

Metric 1-Center in l-infinity norm (when dimension is part of the input)

Consider the following problem, Input: A number $d>0$, $X \subseteq \mathbb{R}^d$. Output: A center $c\in \mathbb{R}^d$ s.t $\max_{x \in X} \lVert x - c\rVert_p $ is minimized. This is the 1-...
3
votes
0answers
78 views

PTIME or NP-Hardness of stochastic objective function

I will begin by linking a previous post where I asked a general question for a stochastic setting which I describe below. It turns out that my "proof" for a restricted case had a mistake and there is ...
0
votes
0answers
66 views

Hypergraph Coloring Complexity

Dear can you help I am confused about the complexity of hypergraph coloring and finding the minimum number of colors Finding the minimum number of colors for strongly coloring a k-uniform hypergraph ...
4
votes
0answers
83 views

Showing hardness of maximizing stochastic objective function over graph

Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$. The challenge is to ...
3
votes
1answer
109 views

Results/concepts that also proved useful outside of their “home areas”

There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used ...
2
votes
1answer
86 views

Clarification regarding Bounded Quadratic Congruence Problem

Given: 3 positive integers $a, b, L$. Problem: Is there a positive integer $x < L$ such that $x^2 \equiv \ a (mod\ b)$? The above problem is NP Complete (as mentioned in G&J) even if we ...
4
votes
0answers
171 views

How hard is APPROXIMATE-#SAT?

It is well known that the problem of counting the satisfying assignments of SAT, namely the problem #SAT, is #P-complete. It is also suspected (somewhat less widely) that even deciding SAT should ...
6
votes
1answer
137 views

Is End-of-Monotone-Line PPAD-complete?

Consider the following problem from TFNP that is somewhere between End-of-the-Line (PPAD) and End-of-Metered-Line (CLS). Input (via polynomial circuit): Graph on vertex set $0$ to $2^n-1$ such that ...
1
vote
0answers
82 views

Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

If you remove LLL part then is remaining part of a. Lenstra algorithm b. Barvinok algorithm in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$...
6
votes
2answers
515 views

a polynomial representation of boolean functions

I came up with this linear transformation to map boolean functions to polynomials and it seems to have some nice properties. I was wondering if there is any reference describing this (and/or similar) ...
1
vote
0answers
85 views

How hard is gapped satisfiability?

It is well known that general satisfiability (of polynomially many clauses) is NP-hard, and in fact, it is conjectured that an algorithm deciding instances of SAT takes time nearly $2^n$ on $n$ ...
2
votes
1answer
117 views

Is there any time efficient way of achieving the result of FKS hashing lemma?

FKS hashing lemma states. Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $ $x_j$ mod $p$ if $x_i \neq x_j$...
4
votes
1answer
253 views

If a root||nonce Proof-of-Work certificate is prime, can it be used in any other interesting proofs?

Because Bitcoin and many other cryptocurrency mining certificates are "rare" in that their respective hash is less than a very small number, can we leverage their rarity in probabilistic proofs of ...
3
votes
3answers
469 views

Why is the circuit class AC0 unavoidable?

Take AC0. What is a natural thought process that leads to the definition of AC0? Does this class arise intrinsically anywhere? My problem is that in the case of unbounded fan-in, AND and OR gates ...
4
votes
0answers
65 views

Complexity of comparing polygon perimeters

The problem of comparing the lengths of two paths of line segments connecting points in $\mathbb{Q}^2$ is not known to be in $\text{P}$, nor even in $\text{NP}$. Does requiring that the paths begin ...
3
votes
1answer
154 views

Proof that all Boolean functions can be computed by $(MOD_2-MOD_3)$ circuit

I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-...