Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,674
questions
-1
votes
0answers
11 views
Complexity of finite difference method
if I have a function $f:\mathbb R^N\to \mathbb R$ and i would like to compute all the partial derivatives of $f$ w.r.t. the $N$ input, which is the computational complexity using the (ones sided) ...
3
votes
1answer
45 views
What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper
I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that:
To the best of our knowledge, ...
-1
votes
1answer
76 views
Time complexity for multiplying two lower triangular matrices
I was wondering, if multiplication of two $n \times n$ lower (or upper) triangular matrices has a more efficient algorithm than multiplication of two general $n \times n$ matrices?
$$
\begin{bmatrix}
...
-5
votes
0answers
32 views
What is the efficiency of this javascript algorithm?
I wrote a really cool code sample which I will include at the end of this question. It completes in O(N) time in the javascript engine according to my debugging tools, but solves the boolean ...
2
votes
0answers
101 views
Proof systems induced by NP-complete problems
Satisfiability is the fundamental NP-complete problem. Cook-Reckhow theorem states that the existence of a propositional proof system that admits polynomial size proofs for all tautologies implies ...
11
votes
3answers
371 views
Applications of sunflower lemma in theoretical computer science
In one lecture by Kewen Wu who is one of the authors of paper
Improved bounds for the sunflower lemma,
it is said that the sunflower lemma can be applied to many fields like
circuit lower bounds
...
-2
votes
0answers
39 views
performance vs complexity given an optimization problem
Newbie here.
I want to read a few papers on the theory of the performance of an algorithm vs its complexity for a given problem. I will give an example shortly but my aim is to find papers, books, ...
7
votes
1answer
311 views
Technical lemma about curves used in original proof of PCP theorem
I am reading the proof from here and found a technical lemma that seems to be incorrect (its proof is short and very vague). I know this is rather specific and the context is problematic, but I couldn'...
5
votes
0answers
130 views
What research is being done in classical complexity theory?
As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
0
votes
0answers
44 views
Can we multiply two numbers more efficiently (using binary circuits) if one of the numbers is fixed? [duplicate]
Let $a_1, a_2 \dots$ be a sequence of natural numbers, where $a_i$ has bit length $i$. Consider a function $f_n : \{0, 1\}^n \to \{0, 1\}^{2n}$ defined as $f_n(x) = a_n \cdot x$ ($\cdot$ is ...
2
votes
0answers
94 views
Is PP invariant under changing its cut-off from 1/2 to another number?
Suppose I have a fixed family of quantum circuits $\{C_i\}$ for which determining whether the maximum output acceptance probabilities are $p\geq 1/2$ or $p< 1/2$ is PP-hard.
Now suppose I have the ...
0
votes
2answers
103 views
Order of quantifiers in the definition of NP-completeness: does the reduction allow arbitrary polynomials? [closed]
Arora and Barak define NP-completeness as the following:
"We say that a language $A \subseteq \{0, 1\}^∗$
is polynomial-time Karp reducible to a language
$B \subseteq \{0, 1\}^∗$
denoted by
$A \leq_p ...
4
votes
1answer
114 views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
0
votes
0answers
79 views
Are there complexity theory consequences of the collapse NEXP=EXP^NP?
It is clear that $NEXP\subseteq EXP^{NP}$, as a TM with exponential run time can simply query the NP oracle with an exponentially long query. However, it's not clear that the reverse $EXP^{NP}\...
2
votes
0answers
89 views
Complexity of a scheduling problem with a fixed left bound of jobs
Consider the following scheduling problem. We have a finite set of jobs $\mathcal{J}= \{j_1, j_2, ..., j_n\}$ to do. Every job $j_i$ has its own value $c_i$ (the amount of money we are paid for ...
2
votes
1answer
96 views
What is the computational complexity of Acyclic Joins?
I am quite new to relational algebra, but I realize that there are efficiency proofs for processing Acyclic joins. I have not been able to understand these results, but this particular problem is ...
7
votes
5answers
345 views
NP-complete decision problems on deterministic automata
Do you know any NP-complete decision problems on deterministic automata? Most NP-complete problems that come to my mind are either (see, or here) graph theoretical, or involve some string rewriting or ...
2
votes
1answer
56 views
FO(TC) lower bounding games?
Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for $FO(TC)$ formulae? I am aware of EF games as they apply to first-order and second-order statements, but ...
1
vote
0answers
68 views
existence & characterization of “kolmogorov efficient” programs
$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$
Disclaimer: I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard ...
3
votes
1answer
112 views
$DTIME_1(o(n^2))\setminus$ REGULAR
Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time.
Help!
Related paper: On the structure of ...
10
votes
0answers
128 views
Alternative proofs of Savitch's theorem?
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?
By the usual one I mean the proof based on recursively querying whether there is a midpoint.
...
2
votes
1answer
109 views
Complexity of solving systems of linear equations with hash preimages
Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are ...
1
vote
1answer
50 views
Matrix rank approximation
I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following:
What is the status of approximating rank of a ...
5
votes
1answer
117 views
Complexity of finding automorphism group of code
What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for ...
2
votes
1answer
155 views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
2
votes
2answers
162 views
Problem in deterministic time $n^p$ and not lower
I'm looking for any language $L$ candiate to be in $DTIME(n^p) -DTIME(n^{p-1})$ (it takes at least $n^{p-1}$ steps to determine if an input is in L with a 2-tape $TM$, but L is polynomially solvable).
...
7
votes
1answer
121 views
The complexity of the permanent of low rank matrices
I know that for an arbitrary $n \times n$ matrix, Ryser's algorithm can compute the permanent in $\mathcal{O}(2^n n^2)$ time. I'm interested in computing the permanent of $n \times n$ matrices of rank ...
-1
votes
1answer
66 views
the shorstest cycle containing two given points
I am given a edge-weighted (multi)graph $G$ and two of its vertices, $u, v\in V(G)$. I want to find two edge-disjoint paths that connects $u$ and $v$ while minimizing the sum of the lengths of the ...
0
votes
1answer
87 views
Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?
We conjecture that Hamiltonian cycle is fixed parameter tractable with parameter clique cover, given $k$-clique cover.
Let $G$ be connected simple graph.
$k$-clique cover of graph $G$ is partition ...
11
votes
3answers
2k views
“Almost all objects have property P” vs. “It is easy to test whether an object has property P”
I am interested in any relation between "almost all objects(from a universe) possessing a particular property P" versus "testing whether an object has property P being poly. time decidable".
My guess ...
0
votes
1answer
90 views
Is the counting version of 1-in-3 Sat #P-complete?
In the paper "Hard Tiling Problems with Simple Tiles", Moore and Robson prove that Cubic Planar Positive 1-in-3 Sat in NP-complete by a reduction from Positive 1-in-3 Sat.
Cubic Planar Positive 1-in-...
0
votes
0answers
46 views
Randomized Reduction for Maximization Problem
I have two maximization problems $P_1$ and $P_2$ where the decision version $L_1 = \{(x, t) : \operatorname{Val}_1(x)\ge t\}$ of $P_1$ is $\mathsf{NP}$-complete. Let $f:P_1\to P_2$ be a randomized ...
4
votes
1answer
213 views
Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?
This is another attempt to formalize my former question on the topic.
I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
0
votes
1answer
179 views
Does two-sided error have more capability than one-sided error?
From $P=RP$ extrapolation we might think $EXP=REXP$.
What evidence do we have $BPP\subseteq REXP$?
What consequence $REXP\subseteq BPP$ gives other than what $EXP\subseteq BPP$ gives?
2
votes
0answers
89 views
How fast can we perform DFT on a Log-RAM computer?
The question is how fast we can perform an $n$ coefficient discrete Fourier transform on the log-RAM model of computation. If we assume that we can do arithmetic operations on registers of size $\log{...
3
votes
0answers
88 views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete:
Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$?
The reference provide was to the textbook “Computers and ...
4
votes
0answers
148 views
Witness verifiable quantum advantage
Update: A slightly different version of this question has been answered here.
As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
...
7
votes
1answer
383 views
Quantum Money where not even the Bank can counterfeit
The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties:
The bank can produce bank notes in the form of quantum states.
Anyone can verify that ...
2
votes
0answers
54 views
Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?
Can the $\mathsf{P}^{\#\mathsf{P}}$ (= $\mathsf{P}^{\mathsf{PP}}$) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a $\...
1
vote
1answer
81 views
The decision procedure of theory of closed real field is in NP-hard?
The decision procedure of theory of closed real field refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers
2
votes
1answer
49 views
Maximum subgraph problem with unknown complexity
Let $Q$ be a polynomial time decidable graph property. In a graph let us call a subgraph $S$ a $Q$-subgraph, if $S$ has the property $Q$. Consider the following optimization problem:
Maximum $Q$-...
9
votes
1answer
157 views
What is the complexity of checking equivalence of two boolean formulae without NOT symbol?
Suppose I have two boolean formulae (propositions) $P_1$, and $P_2$ (can be assumed to be in CNF) over the same variables and such that there are no "NOT" symbols used. I.e. only conjunction and ...
9
votes
2answers
113 views
Complexity of finding an edge set yielding specified vertex degrees
I'm trying to figure out if the following two problems are known in general to be in P or NP-complete:
Q1: Given a graph $G=(V,E)$ and integers $d_i,\,1\leq\,i\leq|V|$, does there exist a subset $E'...
4
votes
0answers
127 views
Terminology: FNP, with P replaced by NP?
Consider these two classes of search problems:
Search problems with poly-sized solutions s.t. verifying solutions is in P.
Search problems with poly-sized solutions s.t. verifying solutions is in NP.
...
3
votes
0answers
110 views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
4
votes
1answer
281 views
Consequences of BPP=BQP
If BPP=BQP then there is a polynomial time randomized factoring algorithm. A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, ...
1
vote
0answers
63 views
Time complexity of alternation free quantified linear program with no free variables and only existential quantifications
We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program.
I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
9
votes
0answers
131 views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
5
votes
1answer
94 views
Is the isomorphism problem between posets represented by DAGs GI-complete?
Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?
I believe this problem is equivalent to ...
5
votes
1answer
211 views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
