# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,871 questions
Filter by
Sorted by
Tagged with
29 views

### Short UNSAT Certificates for X3SAT

Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
15 views

### How can I calculate the computational complexity of an equation composed of 2n multiplications and 2nm^2 additions?

I want to calculate the computational complexity in term of the big (O). My equation is: It composed of 2n multiplications and 2nm^2 additions. The complexity of this equation is it O( 2n + 2nm^2 ) ...
61 views

### Are there classes for that FO-model checking is FPT on hypergraphs?

For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al. Are there similar results for ($k$-uniform)...
• 41
121 views

### For VCP and fixed value k, what's the result if we prove optimal value > (n/2)+(n/k) or we can produce a feasible objective value < (kn)/(k+1)?

I wrote a new idea (by a combination of a well-known SDP formulation and a randomized procedure to conclude that for the Vertex Cover Problem the optimal value > (n/2)+(n/k) or we can produce a ...
63 views

I was following a research paper which have the following equation: $\left(1-\frac{1}{K}\right)^{K-i}\left[1-\left(1-\frac{1-p}{K}\right)^{i}\right]=\frac{i(1-p)}{K}+O\left(\left(\frac{i}{K}\right)^{2}... • 89 6 votes 0 answers 101 views ### Computing permanents when we are promised that the value of the permanent is large Suppose you are given an$n$by$m$real matrix (or even complex matrix) with orthonormal rows. ($m=poly(n)$, say$m=n^2$.) For an$n$-tuples of columns (with repetitions) from M we consider the ... • 5,933 2 votes 0 answers 47 views ### Pebble games and conversions to bounded width circuits Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits? Here, "conversions to bounded width circuits" means that circuits ... 2 votes 1 answer 120 views ### Complexity of the Complete (3,2) SAT problem? A complete$k$-CNF formula is a$k$-CNF formula which contains all clauses of size$k$or lower it implies. Deciding the satisfiability of a$k$-CNF formula is clearly a tractable problem since a$k$-... • 1,069 2 votes 0 answers 75 views ### Nondeterministic polynomial time languages with linearly bounded certificates Define the class$X$of languages by the condition that a language$L$over alphabet$\Sigma$is in$X$iff there are a constant$c > 0$and a polynomial-time checking relation$R$such that for ... • 91 5 votes 0 answers 74 views ### Complexity of approximating boolean functions with circuits Let$f$be a boolean function on$n$variables - say we want to find the smallest circuit$C$where$C(x)=f(x)$for all but an$\epsilon$fraction of inputs$x \in \{0,1\}^n$. What is known about the ... 0 votes 1 answer 53 views ### Parameterized complexity of Hitting Set with slightly bigger parameter The Hitting Set problem, when parameterized by the size$k$of the hitting set, is W[2]-hard. Is it also W[2]-hard when parameterized by$k$plus the number of subsets in the instance? I explain in a ... • 469 0 votes 0 answers 73 views ### Does NP-completeness in one graph class imply not NP-intermediate in another graph class? I am trying to wrap my head around implications of CSP dichotomy theroem. CSP is short for Constraint Satisfaction Problem. The following seem to be known results (I shall focus on decision problems ... • 1,603 0 votes 0 answers 51 views ### Does the the equivalence of Total variation distance formulas assumes that the two distributions are symmetrical? Does the the equivalence of Total variation distance formulas presented here(https://ece.iisc.ac.in/~parimal/2019/statphy/lecture-14.pdf) assumes that the two distributions are symmetrical ? • 1 2 votes 0 answers 57 views ### Is k-ACYCLIC COLOURABLITY in CSP? All graphs in this question are finite, simple and undirected. Let$k$be a fixed positive integer. A$k$-colouring of a graph$G$is a function$f\colon V(G)\to\{1,2,\dots,k\}$such that$f(u)\neq f(...
• 1,603
58 views

Specifically I'm thinking about NC$^1$/poly and NC$^1$/rpoly (randomized advice). Are there any statements like "If $\{C_n\}$ is a family of NC$^1$/(r)poly circuits with depth $C\log n$, then ...
38 views

### Is Power Dominating Set in W[2]?

I'm interested in the Power Dominating Set problem: given a graph, find a power dominating set $D$ of size at most $k$. A power dominating set is a set of vertices such that it "observes" ...
• 469
77 views

### $\mathrm{AC}^0$ upper bound for Hamming weight

Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says: Any depth $d$ circuit that accepts all $n$ bit strings of Hamming weight $\frac{n}{2} + 1$ and rejects ...
• 153
159 views

### "Addition function" that works for both perm and det simultaneously?

For $f = (f_n)$ a family of polynomials where $f_n$ is a polynomial in $n^2$ variables (which we can think of as the entries of an $n \times n$ matrix), say a function $S(A,B)$ is an addition function ...
• 35.6k
131 views

### Which hypergraphs can be simplified by alternatively removing a hyperedge and an isolated vertex?

Let $H = (V, E)$ be a hypergraph, with $V$ the set of vertices and $E \subseteq 2^V$ the set of hyperedges. An elimination sequence on $H$ consists of alternatively removing hyperedges. Specifically, ...
• 7,350
107 views

### Treewidth relations between Boolean formulas and Tseitin encodings

Suppose you have a propositional formula $\varphi$ in CNF. You want to efficiently obtain an equisatisfiable CNF formula encoding $\neg \varphi$. You use the usual Tseitin encoding with auxiliary ...
• 469
232 views

### Is the following equitable factoring problem $NP$-hard or in $P$?

Consider the following factoring problem: Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
• 12.5k
150 views

### Reductions weaker than polynomial-time for $\exists \mathbb{R}$

I am currently studying the complexity class $\exists \mathbb{R}$ which contains all problems that are reducible in polynomial time to the existential theory of the reals. In the literature ...
• 161
107 views

• 39
84 views

### Simulating a $k$ tape Turing machine with a 2 tape Turing machine

Let $k$ be an (fixed, $3$ for instance) integer, what is the fastest simulation of a $k$ tape Turing machine by a two tape Turing machine? That is we're looking for the best 2 tape TM $U$, such that ...
• 91
101 views

### Question about BPP complexity class [closed]

Good morning everyone, I just started studying the BPP complexity class and the amplification lemma. There is one exercise about BPP that I don't understand, I hope that you can help me. Let $L$ be a ...
167 views

### Order notation quirk

Is it true that $$O(n) = \bigcap \{ O(g) \mid g \in \omega(n) \}?$$ This appears to be a straighforward question about sets of functions, but on closer examination leads to some murky waters. I would ...
• 18.7k
157 views

### $NP=QMA$'s impact on $BPP$ vs $BQP$ problem

$\mathit{BPP}$ vs $\mathit{NP}$ and $\mathit{BQP}$ vs $\mathit{QMA}$ are two problems that are (in spirit, for classical and quantum computers respectively) similar and both are open. Moreover, we don'...
• 801
166 views

### Accessible entry for computational complexity theory through concrete problems

I am planning to start studying computational complexity theory. As the field is technical for a fresh undergrad alumni like me, I thought a good approach is to tackle it through areas I am more ...
66 views

### Interesting Variation on Subset Sum Problem

Does anyone have any ideas for this algorithms problem? Given an array $A$ with 40 integers ($-10^9 < A_i < 10^9$), how many ways are there to reach a target sum $X$. Normally, I would use ...
72 views

### Reducing counting minimal vertex covers to counting minimum cardinality vertex covers

Consider two problems. Problem 1: Given a graph $G = (V, E)$, find the number of minimum cardinality vertex covers of $G$. Problem 2: Given a graph $G = (V, E)$, find the number of minimal vertex ...
• 153
105 views

### Finding planes from their points

Given some points $P=\{x_1,\dots,x_m\}$ in a vector space $(Z/2Z)^n$, if $P$ is a union of linear subspaces all of the same dimension $1<d<n$, can we efficiently find these subspaces? (Any ...
• 4,400
1 vote
167 views

### $\#NAE2SAT$ and $\oplus NAE2SAT$ complexity

Deciding $2SAT$ is in $NL$ and $\#2SAT$ is $\#P$ complete while $\oplus2SAT$ is $\oplus P$ complete. Deciding $SAT$-$2$-$NAE$ - every clause has exactly $2$ literals, is there an $NAE$ satisfying ...
• 12.5k
123 views

### XORSAT to HornSAT reduction

I am trying to write a practical piece of code that solves a XORSAT by first reducing it to HornSAT and then solving the HornSAT (instead of doing Gaussian Elimination over F2). The reason for this ...
369 views

### Examples of simulations in proof complexity that are not p-simulations

I am writing a paper on the complexity of some unorthodox proof systems, where I have two systems $P$ and $Q$ such that $P$ simulates $Q$ in the sense of it being possible to translate a $Q$-proof ...
• 191
350 views

### Invisible electric fence even if P = NP?

Scott Aaronson has suggested that one argument in favor of $\mathsf{P} \ne \mathsf{NP}$ is that there seems to be an invisible electric fence separating $\mathsf{NP}$-complete problems from problems ...
• 7,073
1 vote
111 views

### Is counting the union of power sets NP-complete?

Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$. We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-...
48 views

• 486