Top Questions

10 votes
1 answer
306 views

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

-2 votes
0 answers
21 views

Can infinite regular languages be prefix-free?

35 votes
6 answers
6k views

Fast Reduction from RSA to SAT

5 votes
2 answers
108 views

Modify DCFG to enforce length limit

3 votes
1 answer
154 views

What is the 'P=NP?' building?

4 votes
3 answers
123 views

Why is order/choice an issue for a logic for PTIME

3 votes
1 answer
210 views

Ignore side effect in monadic code

-1 votes
1 answer
60 views

What is a model theory / category theory basis of System F-omega that corresponds to what programmers actually do?

1 vote
1 answer
70 views

What are some practical applications of inductive-inductive and inductive-recursive types?

3 votes
1 answer
60 views

Deciding if max-cut with negative edge weights has a solution with positive value

1 vote
1 answer
110 views

How to calculate processor throughput boundary in CSAPP?

8 votes
1 answer
296 views

Positive cut algorithm on bipartite graphs with negative weights

5 votes
0 answers
83 views

Proof complexity of Sudoku

29 votes
3 answers
3k views

Does there exist an extension of regular expressions that captures the context free languages?

-2 votes
0 answers
66 views

Kindly find a flaw in my argument for why there can't be a super intelligent AI from Computational Complexity considerations [closed]

0 votes
1 answer
83 views

complexity of the maximum rank correlation

4 votes
1 answer
122 views

Intersection Non-Emptiness for Two-Way Finite Automata

0 votes
1 answer
221 views

Where to read about PSO (partial store order) memory model

0 votes
0 answers
55 views

What work on min max connectivity problems has there been?

0 votes
0 answers
20 views

Primitive Optimal Solution [closed]

5 votes
5 answers
4k views

Is there such a thing as a state-based programming language?

13 votes
4 answers
824 views

A Multi-cut Problem

1 vote
1 answer
74 views

Formalising Church numerals in Agda

0 votes
0 answers
32 views

Turing 1936 Skeleton Tables Procedure

3 votes
1 answer
155 views

Polynomial Identity Testing for $\prod \sum \prod$

1 vote
0 answers
88 views

Induced subgraphs with interface

0 votes
0 answers
58 views

Is checking at least $k$ solutions as hard as counting? [closed]

0 votes
2 answers
37 views

Combining different length epsilon-ADU hash function families

-1 votes
2 answers
137 views

Help understand why FOL wff are enumerable, but FOL is undecidable

43 votes
5 answers
7k views

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

2 votes
0 answers
66 views

Im looking for papers to read to strengthen my understanding of overall cs theory

-2 votes
0 answers
27 views

aproximation of set cover of bounded size [closed]

0 votes
1 answer
37 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

8 votes
1 answer
345 views

In logic programming, what would a language with second-order model theory gain?

0 votes
0 answers
32 views

Bipartite Matching with a Partition Constraint over the Vertices

0 votes
0 answers
61 views

Has multiobjective prize collecting steiner tree or TSP been studied?

0 votes
1 answer
24 views

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

2 votes
1 answer
27 views

Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

-2 votes
0 answers
30 views

Could QR codes be used in tandem with Conway's Game of Life be used for compression? [closed]

1 vote
3 answers
123 views

Stable/Robust Traveling Salesman Approximation Methods

4 votes
1 answer
108 views

Straight-line program for sets

4 votes
0 answers
88 views

Higher dimensional automata?

2 votes
0 answers
48 views

Do prefix hash functions work well for approximate counting?

0 votes
0 answers
78 views

Proof of coNE ⊆ NE/poly

4 votes
0 answers
85 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

15 votes
3 answers
573 views

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

0 votes
1 answer
166 views

This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

1 vote
0 answers
39 views

Is the Maximum Coverage Problem Remains as Hard when Taking Most Sets?


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