Vor's user avatar
Vor's user avatar
Vor's user avatar
Vor
  • Member for 10 years, 8 months
  • Last seen more than a week ago
23 votes
3 answers
3k views

Is rejection sampling the only way to get a truly uniform distribution of random numbers?

22 votes
1 answer
2k views

Classification of intractable/tractable satisfiability problem variants

17 votes
1 answer
3k views

Planarity conditions for Planar 1-in-3 SAT

15 votes
0 answers
277 views

Using logic to prove non-regularity of a language

13 votes
2 answers
2k views

Decidable restrictions of the Post Correspondence Problem

11 votes
2 answers
569 views

Job scheduling with a bottleneck problem

11 votes
3 answers
856 views

Introductory book on Logic and Computation

9 votes
0 answers
94 views

Interval density of time bounded Kolmogorov complexity

9 votes
2 answers
441 views

Complexity of a subset sum variant

9 votes
2 answers
740 views

A variant of the busy beaver function

8 votes
1 answer
718 views

Kolmogorov complexity of string concatenation

8 votes
2 answers
906 views

Reduction examples from the strongly NPC problem 3-PARTITION

6 votes
1 answer
159 views

Matrix equality up to row/column permutations problem name

6 votes
0 answers
124 views

Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

6 votes
1 answer
109 views

Busy Beaver machines on semi-infinite tape

5 votes
1 answer
77 views

Tag system variant

5 votes
1 answer
155 views

Techniques/tools for constructing hard instances of a puzzle game

5 votes
2 answers
168 views

Numeral systems other than unary used in nature or in animal and human behaviours

4 votes
1 answer
630 views

Time complexity of an enumeration of SUBSET SUM instances

4 votes
1 answer
491 views

Name of an Exact Cover by 3 sets variant

4 votes
2 answers
1k views

Hardness proof of EVEN-ODD PARTITION

4 votes
2 answers
81 views

Defining $a^n b^{n^2}$ with one existential SO binary relation

3 votes
0 answers
53 views

Conditions that imply closure under intersection of context-free languages

2 votes
1 answer
82 views

Context free languages invariant by "shuffling" right hand side

2 votes
1 answer
52 views

"Print 'em all game" for Turing machines

2 votes
0 answers
77 views

NPDA, guessing capability and stack as an exclusive resource

2 votes
0 answers
111 views

Karp reduction between FACTORING and a variant of it

1 vote
1 answer
82 views

Complexity of testing if a number is a primorial

1 vote
2 answers
108 views

Is there a name for this infinite language?

1 vote
0 answers
226 views

Quick testing tool for context sensitive grammars