Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,871
questions
0
votes
0
answers
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 ...
- 499
-4
votes
0
answers
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 ) ...
- 93
4
votes
0
answers
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
-3
votes
0
answers
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 ...
0
votes
0
answers
63
views
Simplify or bound using Big-O notation
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 ...
- 689
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 ...
- 51
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
2
votes
0
answers
58
views
Does advice reduce depth?
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 ...
- 21
0
votes
0
answers
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
3
votes
1
answer
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
8
votes
0
answers
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
2
votes
0
answers
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
4
votes
1
answer
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
3
votes
0
answers
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
6
votes
1
answer
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
2
votes
1
answer
107
views
Complexity of finding approximate solutions for systems of polynomial equations
Consider the following problem:
Input: $(p_1,...,p_n, \epsilon)$ where each $p_i$ is a polynomial in $m$ variables with integer coefficients and $\epsilon>0$.
Output: If there is $(r_1,...,r_m) \in ...
- 23
1
vote
1
answer
139
views
Nontrivial Algorithms for Coloring (Parameterized by Pathwidth)
Let $k$ be a positive integer. In the $k$-coloring problem, we are given a graph $G$ on $n$ nodes, and want to determine if there is a way to assign a color to each vertex of $G$ such that no two ...
- 454
2
votes
0
answers
63
views
Relationship b/w $QMA$ and $QCMA$
I was trying to read and understand about the complexity classes $QMA$ and $QCMA$:
$QMA$ is defined as the class with the set of problem such that, given a quantum certificate for any problem, its ...
- 294
1
vote
1
answer
87
views
Bounded non-emptiness intersection of deterministic context-free grammars
Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length ...
- 11
0
votes
0
answers
98
views
How can I switch into computability theory when I am part way through my PhD in deep learning?
I am partway through my PhD studying deep learning. I chose it just because it's useful and would yield a lot of industry opportunities. However, I am really missing my previous coursework in ...
- 101
3
votes
0
answers
65
views
Complete problems for fast-growing hierarchy classes
I need examples of natural complete problems in classes $\textbf{F}_\alpha$, definition of $\textbf{F}_\alpha$ can be found here. Also in section 6 there are examples for $\omega$, $\omega^\omega$, $\...
- 39
4
votes
0
answers
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
0
votes
1
answer
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 ...
- 13
7
votes
1
answer
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
2
votes
0
answers
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
2
votes
0
answers
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 ...
-3
votes
1
answer
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 ...
4
votes
0
answers
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
5
votes
1
answer
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
0
answers
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
3
votes
1
answer
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 ...
- 31
9
votes
0
answers
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
11
votes
0
answers
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
0
answers
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-...
3
votes
0
answers
48
views
Hardness of computing entropy of a function on uniform input distribution
Let $p \geq q \in \mathbb{N}_+$, and let $L_\mathsf{max-entropy} := \{(f,k) \in \{0,1\}^{\lambda^p} \times \{0,1\}^{\log\lambda} | \lambda \in \mathbb{N} \wedge \mathrm{H}(\underbrace{C_f(\mathcal{U}_{...
0
votes
0
answers
67
views
SAT to k-in-3-SAT reduction
Given a 3-SAT clause. Is there a way to convert 3-SAT to k-in-3-SAT such that:
The number of new variables introduced are less than the number of clauses (without adding dummy clauses etc.)?
The ...
- 294
-1
votes
1
answer
119
views
Polynomially solvable 3-SAT problem instances [closed]
Given the 3-SAT problem with $v$ variables and $c$ clauses:
Is there a clause to variable ratio for which the 3SAT problem is 'easy' i.e. solvable in polynomial time?
We are assuming the 3-SAT ...
- 801
2
votes
2
answers
180
views
Separating 2-SAT from Clique
Since the P vs. NP problem is still an open problem, 2-SAT and Clique might both be in P if P = NP. Is there any known complexity measure whatsoever that is already mathematically proven to ...
- 414
0
votes
0
answers
83
views
Computational complexity of Private Computation
In a recent work (Sun2017), Sun and Jafar defined the Private Computation (PC) problem where a user wants to compute a function of $K$ datasets, using $N$ distributed and non-colluding servers, ...
- 190
11
votes
2
answers
828
views
Randomized algorithms not based on Schwartz-Zippel
Are there any problems that are known to be in a randomized complexity class (e.g. RNC, ZPP, RP, BPP, or even PP), but not in any lower non-randomized class (e.g. NC, P, NP), and whose membership in ...
- 5,246
0
votes
0
answers
37
views
Query in the proof of greedy manipulation theorem (of a voting scheme)
Paper being referred to: http://www.cs.cmu.edu/~arielpro/15896/docs/paper9.pdf (The Computational Difficulty of Manipulating an Election).
I have a query in Theorem 1 of this paper; specifically, in ...
1
vote
0
answers
52
views
Natural problems believed to be in EQP but not BPP
Are there any “natural” problems in $\mathsf{EQP}$ that are believed to not be in $\mathsf{BPP}$? If so, what are some exapmles?
- 486
5
votes
1
answer
221
views
Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?
Some classes, such as ALL, ELEMENTARY, and R, are very badly behaved when used as oracles. For instance, all three of these classes trivially collapse P and EXP, even though (by the Time Hierarchy ...
- 486