Skip to main content

Top Questions

2 votes
2 answers
74 views

Can a RAM machine with polynomial memory be simulated by a multi-tape Turing machine without extra time or space costs?

4 votes
1 answer
32 views

Complexity of finding graph automorphism group vs. canonization

0 votes
0 answers
11 views

Integration of analytic function

0 votes
0 answers
21 views

NP-completeness of Nested Flexible Machine Scheduling with summaric job completion time

17 votes
1 answer
468 views

Strongly Regular Graph and GI-Completeness

2 votes
1 answer
58 views

Is $D_\infty$ a universal domain?

18 votes
4 answers
4k views

What would be the consequences of $\mathsf{PH=PSPACE}$?

0 votes
1 answer
71 views

Are Turing Machines Models?

2 votes
0 answers
37 views

Work-efficient parallelization of matrix chain multiplication?

-2 votes
0 answers
34 views

Big O of evaluating expression under RAM model

1 vote
0 answers
23 views

On generating tight instances of Max Cover / NP-hard Problems

3 votes
0 answers
87 views

References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$

-1 votes
0 answers
34 views

Applying $/mu$-Operator for Unbounded minimization

2 votes
1 answer
90 views

Classical Fourier analysis for the nonabelian hidden subgroup problem

4 votes
1 answer
201 views

Complexity of permutation group intersection

5 votes
2 answers
247 views

What are the computations model with a constant slowdown ? (and why do we care about Turing machines)

3 votes
0 answers
98 views

Collapse of query and oracle hierarchies

2 votes
0 answers
76 views

Multipoint evaluation in Lagrange basis

7 votes
1 answer
250 views

Is parity of GI easy?

10 votes
1 answer
332 views

Is there a planar 4-regular graph that is 3-acyclic colourable?

0 votes
0 answers
22 views

What would be the time/approx.-complexity of making a special graph into hole-free?

1 vote
0 answers
124 views

Testing monotonicity for functions of the form $f :\{0,1,2\}^n\rightarrow \{0,1\}$

1 vote
0 answers
34 views

Clause Density for guaranteed Easy (2, 3) SAT Cases

1 vote
0 answers
22 views

Bounds on the problematic number of threads

2 votes
1 answer
132 views

Complexity of 2-coloring with extra constraints

4 votes
1 answer
85 views

Solving #SAT through TQBF

44 votes
5 answers
7k views

What is the smallest Turing machine where it is unknown if it halts or not?

0 votes
0 answers
33 views

Dependence of lossless compression (e.g. Lempel-Ziv) on string length and alphabet size

0 votes
1 answer
145 views

Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

4 votes
0 answers
61 views

EXPSPACE-complete optimization problems

0 votes
0 answers
31 views

Reduction from any succinct language to tiling

1 vote
2 answers
145 views

Use of transitive closure in proof of NC hierarchy collapse

-2 votes
0 answers
48 views

Graphs, given a vertex find shortest even path with each of the other vertices

6 votes
1 answer
116 views

Are there any books or articles that contain information on the P weak omega or second order predicate calculi?

4 votes
1 answer
451 views

Why can't CVP be trivially reduced to SVP by shifting?

-2 votes
0 answers
65 views

Parallel complexity of modular inverse of $2^t\pm i$

-1 votes
1 answer
176 views

How close is a Boolean function from being a linear boolean function?

3 votes
0 answers
80 views

What does Håstad verifier query?

0 votes
0 answers
40 views

What rules govern when combinators (e.g. S, K, and I) can be only partially applied?

2 votes
1 answer
110 views

Encoding of nodes in Binary Decision Diagrams

19 votes
1 answer
502 views

Are there other proofs for Barrington's theorem?

-1 votes
1 answer
45 views

is the set of all numbers that sum up a subset sum problem a one way function?

2 votes
0 answers
88 views

Minimizing a submodular function containing summation and production under partition matroid constraint

12 votes
3 answers
509 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

1 vote
0 answers
37 views

Contraction in belief revision

7 votes
0 answers
115 views

Are there any programming languages based on the method of analytic tableaux, aside from Fitting's Proflog?


Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.