Skip to main content

Computer Science

Top Questions

Active Hot Week Month

5 votes

1 answer

631 views

Are definite languages closed under Kleene Star?

Emil Jeřábek's user avatar

4,536

answered Oct 19 at 13:50

5 votes

2 answers

149 views

How is $\overline{SAT}$ not obviously in NP?

Sebastian Mueller's user avatar

Sebastian Mueller

126

modified Nov 3 at 0:07

2 votes

1 answer

393 views

Understand the Levin reduction

templatetypedef's user avatar

templatetypedef

9,332

modified Nov 10 at 2:12

1 vote

2 answers

216 views

Why move memory from LLM to MCP?

machine-learning

meBe's user avatar

meBe

39

modified Oct 27 at 0:01

1 vote

1 answer

183 views

Polynomial hierarchy, many-one reduction, but with co-NP subroutine

Community's user avatar

1

modified Oct 21 at 9:05

0 votes

1 answer

111 views

Runtime analysis of Fibonacci series

Emil Jeřábek's user avatar

4,536

answered Oct 28 at 13:32

2 votes

1 answer

105 views

Understanding the ⊢ notation and context in Natural Deduction vs Sequent Calculus

Emil Jeřábek's user avatar

4,536

modified Nov 14 at 10:06

0 votes

1 answer

41 views

What is this asymptotic equivalence called?

asymptotics

Emil Jeřábek's user avatar

4,536

answered Nov 4 at 11:55

2 votes

1 answer

88 views

Proving NPhardness of linkedin queens

fiktor's user avatar

141

answered Oct 26 at 21:40

3 votes

1 answer

65 views

Why are type theory's foundational claims so broad, and is ruling out "meaningless" expressions a mistake?

Chaos's user avatar

672

answered Nov 7 at 16:24

0 votes

1 answer

49 views

Fast algorithm to find factor of a term that is a power

Emil Jeřábek's user avatar

4,536

answered Nov 9 at 18:12

1 vote

1 answer

75 views

What complexity implications are there from not being in a abstract family of languages?

formal-languages

D.W.'s user avatar

D.W. ♦

169k

answered Oct 24 at 8:44

3 votes

1 answer

44 views

Show that the network reliability problem is NP-complete

Ainsley H.'s user avatar

18k

answered Nov 8 at 19:20

0 votes

1 answer

47 views

Definition of search-NP and search-P

Emil Jeřábek's user avatar

4,536

answered Nov 10 at 9:51

1 vote

1 answer

58 views

What does two-shingle mean in binary trees?

Chaos's user avatar

672

answered Nov 5 at 23:06

0 votes

1 answer

21 views

Demonstrate that this language is regular using pumping lemma

finite-automata

pepper's user avatar

11

0 votes

1 answer

50 views

Can Church numerals division be defined in direct top-down manner?

Will Ness's user avatar

386

modified Nov 10 at 22:20

1 vote

0 answers

62 views

Prove that $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL

A. G.'s user avatar

11

modified Nov 7 at 14:37

1 vote

2 answers

46 views

Regularity of Languages $L_1$ and $L_2$

Nathaniel's user avatar

18.5k

modified Oct 19 at 6:01

0 votes

1 answer

44 views

Best strategy with limited ability of memoization

A. G.'s user avatar

11

modified Nov 8 at 16:27

1 vote

0 answers

56 views

A Fast Polynomial Multiplication Using only Integers for AKS Algorithm

minh quý lê's user avatar

651

modified Nov 5 at 4:17

0 votes

1 answer

43 views

Scheduling Training for Two Dogs with Rest Constraints

fiktor's user avatar

141

answered Oct 26 at 18:49

0 votes

1 answer

32 views

Notation for element within an array range

Nathaniel's user avatar

18.5k

answered Oct 24 at 19:04

-1 votes

1 answer

41 views

Master Theorem for this equation

algorithms

Gabriele's user avatar

1

modified Nov 1 at 7:26

0 votes

0 answers

48 views

Find the largest subset of chords in which every pair intersects

finder's user avatar

1

modified Nov 1 at 20:32

0 votes

0 answers

44 views

A computing machinery using a continuous memory tape

Yigit's user avatar

11

asked Oct 23 at 10:57

0 votes

1 answer

31 views

Is the language A = { w#x∣ w , x ∈ { a , b }* and x is a substring of w } context-free?

Li-yao Xia's user avatar

1,465

answered Oct 31 at 7:29

0 votes

0 answers

36 views

Are there exceptions where a grammar is left-recursive or not left-factored but still LL(1)?

https_guru's user avatar

45

asked Oct 25 at 13:28

2 votes

0 answers

36 views

Find all non-extendable ranges in an array of real values with a non-positive sum

cebir latis's user avatar

21

modified 2 days ago

0 votes

1 answer

28 views

Linear programming question

linear-programming

fiktor's user avatar

141

answered Oct 26 at 22:17

1 vote

1 answer

21 views

Optimal in-place suffix sorting algorithm on read-only general alphabets produces wrong results

Fabrizio Apuzzo's user avatar

Fabrizio Apuzzo

131

answered Oct 22 at 8:47

0 votes

0 answers

34 views

How is it possible to implement a zero-address instructions Von Neumann CPU?

danshat's user avatar

1

asked Nov 11 at 9:03

1 vote

0 answers

33 views

Is there an efficient algorithm to reduce the degree of a multivariate polynomial given a list of monomial substitutions?

D.W.'s user avatar

D.W. ♦

169k

modified yesterday

0 votes

0 answers

30 views

What is the best case search time complexity for a radix search trie?

Captain Chicky's user avatar

101

asked Oct 23 at 1:01

0 votes

0 answers

29 views

A twist on previous smaller element

stacks

user1583861's user avatar

1

modified Oct 19 at 2:59

1 vote

0 answers

28 views

Why Can't We Just Choose $i = p+1$ for $L = \{0^p \mid p \text{ is prime}\}$ to prove that $L$ is not regular

pumping-lemma

Denis's user avatar

121

asked Oct 18 at 18:16

-1 votes

0 answers

27 views

A problem from CESE that I can't find solution [closed]

reference-question

Haoyuzheng He's user avatar

1

modified Nov 14 at 2:27

-2 votes

0 answers

25 views

Algorithm Design Binary Tree

Gabriele's user avatar

1

modified Nov 2 at 21:00

0 votes

0 answers

23 views

Construct NFA accepting strings ending with '11' , '101' , '110'

critzcrieg's user avatar

1

asked Nov 10 at 15:03

-2 votes

0 answers

23 views

Need generator matrix for [20, 7, 10] linear code over GF(4)

coding-theory

Axel Truedson's user avatar

1

asked Oct 22 at 12:14

0 votes

0 answers

20 views

Questions about decidability and streaming algorithm

FORZA INTER's user avatar

1

asked Nov 10 at 15:31

0 votes

0 answers

20 views

j-th smallest element in a min heap

heaps

RAHUL 's user avatar

179

modified yesterday

0 votes

0 answers

18 views

Computer Networking: A top down approach on TDM (need help understanding this)

computer-networks

Manish Pant's user avatar

1

modified Oct 22 at 6:39

1 vote

0 answers

18 views

Hardness for COSET WEIGHT problem in terms of Hamming weight

Manish Kumar's user avatar

209

asked Nov 10 at 11:36

0 votes

0 answers

18 views

How to clearly assign back and front-edges in DFS?

Frenzy Ripper's user avatar

1

modified Nov 7 at 3:31

1 vote

0 answers

17 views

Good algorithm to solve a system of "cyclic" banded linear equations

FusRoDah's user avatar

111

asked yesterday

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