Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

0 votes

Is there a logic without induction that captures much of P?

Let $L \subset K$ be two signatures and $\mathcal{L,K}$ be a nonempty classes of $L$-structures and $K$-structures respectively such that every structure in $\mathcal{L}$ has an expansion in $\...
Siddharth's user avatar
  • 851
1 vote
Accepted

Constructing vector valued boolean circuits from boolean circuits

I doubt it. At least, not in all cases. Suppose that you are working in a circuit model where every function $\mathbb{B}^k\to\mathbb{B}$ can be represented by a circuit with $\le 2^k+1$ gates, say by ...
D.W.'s user avatar
  • 12.1k
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686
12 votes
Accepted

How stringent is the peer review process of ECCC exactly?

ECCC is supposed to reject any paper that is submitted without something that appears to be a proof for all of the main theorems. There is no expectation that a board member is going to check that ...
Eric Allender's user avatar
3 votes
Accepted

Hierarchy of classes between NP and NEXP

$\let\R\mathrm$The nondeterministic time hierarchy theorem, which is the reason $\R{NP\ne NEXP}$ in the first place, immediately gives you infinitely many (even $2^{\aleph_0}$) classes intermediate ...
Emil Jeřábek's user avatar
-1 votes

Time Complexity of KnuthBendixCompletion Algorithm

If you have the algorithm, the Big O complexity can be calculated. What challenges are you facing? There is a P-Complete O(n2) note here https://www.sciencedirect.com/science/article/pii/...
Sunny Armstrong's user avatar
0 votes

Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?

The census functions of unambiguous context-free languages can be computed in polynomial time. However, there exist context-free languages whose census functions are #P1-complete. We also have that ...
user72497's user avatar

Top 50 recent answers are included