User vzn

4

17

votes

3

answers

791

views

Is there a TM that halts on all inputs but that property is not provable?

May 14 '14 at 21:43 cody 7,558

8

14

votes

4

answers

1k

views

Bridge theorems for group theory and formal languages

formal-languages reference-request automata discrete-mathematics group-theory

Dec 29 '16 at 22:23 Community♦ 1

4

10

votes

3

answers

4k

views

Looking for a dictionary of math/CS notation

terminology reference-request education

Jul 11 '13 at 19:49 Heatsink 213

3

5

votes

1

answer

528

views

space complexity of DFA intersection problem

reference-request complexity-classes space-complexity lower-bounds dfa

Nov 8 '15 at 20:13 Community♦ 1

1

5

votes

2

answers

2k

views

does every CFL have an ambiguous CFG?

formal-languages formal-grammars ambiguity

Jun 5 '14 at 15:29 Community♦ 1

3

5

votes

0

answers

122

views

research on OR and AND compression in SAT formulas [closed]

complexity-theory np-complete satisfiability p-vs-np

May 21 '14 at 6:39 Raphael♦ 69.4k

2

5

votes

1

answer

321

views

computer science in the movies as an educational angle

education

Nov 9 '13 at 20:03 Community♦ 1

3

5

votes

2

answers

368

views

What are some applications of binary finite fields in CS?

algorithms reference-request discrete-mathematics applied-theory

Oct 27 '12 at 22:33 Juho 20.8k

1

3

votes

1

answer

158

views

Determining if (infinite) binary language DFAs contain at least 1 prime?

regular-languages automata discrete-mathematics number-theory

Oct 13 '15 at 16:03 Community♦ 1

2

3

votes

1

answer

153

views

“Unusual” coupling between a decision problem and a corresponding optimization problem

complexity-theory reference-request optimization decision-problem

Dec 4 '13 at 18:21 Community♦ 1

3

votes

2

answers

727

views

Enumerating weighted permutations in sorted order problem

algorithms reference-request sorting efficiency enumeration

Nov 18 '13 at 21:03 Juho 20.8k

3

votes

1

answer

768

views

Description of resolution algorithm as it applies to SAT

algorithms complexity-theory reference-request logic np-complete

Feb 18 '13 at 22:02 Community♦ 1

2

votes

1

answer

181

views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

complexity-theory reference-request np-complete reductions p-vs-np

Jul 13 '14 at 14:58 Juho 20.8k

1

2

votes

1

answer

311

views

Building functionally complete boolean circuits out of trinary logic

reference-request logic reductions circuits

Feb 22 '13 at 2:18 Juho 20.8k

2

votes

1

answer

1k

views

Calculating Binet's formula for Fibonacci numbers with arbitrary precision

algorithms discrete-mathematics floating-point arithmetic mathematical-programming

Dec 4 '12 at 9:51 Hendrik Jan 25k

2

1

vote

3

answers

385

views

Are there pseudorandom number generators (PRNG) with no finite period?

reference-request number-theory pseudo-random-generators

Jan 25 '19 at 17:24 Veedrac 852

1

vote

1

answer

447

views

context sensitive language finite or infinite

formal-languages computability reference-request undecidability context-sensitive

Apr 6 '16 at 5:52 D.W.♦ 130k

1

vote

0

answers

26

views

pragmatic way to compute/ search/ match MSBs operation

algorithms time-complexity arithmetic

Jun 10 '15 at 17:22 vzn 10.7k

2

1

vote

0

answers

68

views

Notable decidable operations on context-sensitive languages [closed]

formal-languages reference-request undecidability context-sensitive

May 13 '14 at 16:06 Juho 20.8k

2

1

vote

1

answer

543

views

Blum's speedup theorem in big-O format?

complexity-theory asymptotics

Feb 6 '14 at 8:36 Juho 20.8k

1

vote

0

answers

90

views

Applications of algorithms to stock trading analysis

reference-request machine-learning optimization statistics

Jan 31 '14 at 23:16 Community♦ 1

0

votes

0

answers

96

views

2-depth arithmetic circuits and VP vs VNP

complexity-theory reference-request complexity-classes circuits

Apr 24 '15 at 21:07 vzn 10.7k

0

votes

1

answer

136

views

Decidability of fullness of intersection of a CSL with a regular language

formal-languages computability undecidability

Feb 6 '14 at 16:30 Raphael♦ 69.4k

1

0

votes

1

answer

242

views

Blum's speedup theorem showing unclassifiable complexity languages?

complexity-theory

Feb 6 '14 at 8:36 Juho 20.8k

1

0

votes

1

answer

75

views

graph isomorphism completeness of class X and not-X

graphs graph-isomorphism

Dec 25 '13 at 17:17 Community♦ 1

1

0

votes

1

answer

99

views

proof of convergence in arbitrary precision PRNGs

algorithms reference-request probability-theory pseudo-random-generators random-walks

Nov 19 '13 at 0:38 D.W.♦ 130k

1

-1

votes

1

answer

237

views

what are the basic/typical/common mistakes in P=NP claims? [duplicate]

complexity-theory p-vs-np

Mar 19 '14 at 8:20 Community♦ 1

1

-1

votes

1

answer

2k

views

What is an example for which the purely functional programming approach gives better results than imperative style?

programming-languages functional-programming

Oct 3 '12 at 18:11 Community♦ 1

1

-1

votes

1

answer

190

views

References on collective intelligence with respect to CS applications

reference-request education software-engineering books

Sep 28 '12 at 16:28 Juho 20.8k

1

-2

votes

2

answers

2k

views

complexity of decision problems vs computing functions [closed]

algorithms complexity-theory reference-request time-complexity np-complete

Mar 2 '15 at 0:03 Community♦ 1

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

31 Questions

Is there a TM that halts on all inputs but that property is not provable?

Bridge theorems for group theory and formal languages

Looking for a dictionary of math/CS notation

space complexity of DFA intersection problem

does every CFL have an ambiguous CFG?

research on OR and AND compression in SAT formulas [closed]

computer science in the movies as an educational angle

What are some applications of binary finite fields in CS?

Determining if (infinite) binary language DFAs contain at least 1 prime?

“Unusual” coupling between a decision problem and a corresponding optimization problem

Enumerating weighted permutations in sorted order problem

Description of resolution algorithm as it applies to SAT

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Building functionally complete boolean circuits out of trinary logic

Calculating Binet's formula for Fibonacci numbers with arbitrary precision

Are there pseudorandom number generators (PRNG) with no finite period?

context sensitive language finite or infinite

pragmatic way to compute/ search/ match MSBs operation

Notable decidable operations on context-sensitive languages [closed]

Blum's speedup theorem in big-O format?

Applications of algorithms to stock trading analysis

2-depth arithmetic circuits and VP vs VNP

Decidability of fullness of intersection of a CSL with a regular language

Blum's speedup theorem showing unclassifiable complexity languages?

graph isomorphism completeness of class X and not-X

proof of convergence in arbitrary precision PRNGs

what are the basic/typical/common mistakes in P=NP claims? [duplicate]

What is an example for which the purely functional programming approach gives better results than imperative style?

References on collective intelligence with respect to CS applications

complexity of decision problems vs computing functions [closed]