Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Top Questions

15 votes
4 answers
2k views

Is there a known polynomial time complexity problem with bad constants?

6 votes
2 answers
2k views

What does it mean to prove the halting problem is undecidable "using arithmetization"?

6 votes
1 answer
706 views

Representing binary functions with a finite gate set without exponential blow-up?

4 votes
3 answers
621 views

What is practically preventing us from applying set-theoretic types in engineering?

4 votes
1 answer
703 views

Is Determining the Number of distinct Prime Factors Polynomial?

1 vote
2 answers
364 views

Does there exist an context free language L such that L∩L^R is not context free?

0 votes
1 answer
235 views

What is the simplified form of this big o

-2 votes
2 answers
167 views

Could this novel algorithm be qualified to be published in Nature or Science

2 votes
1 answer
90 views

Optimal torch placement in voxel games

2 votes
2 answers
108 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

-3 votes
1 answer
102 views

If Q* can break encryption would that prove P=NP?

3 votes
0 answers
126 views

Recover unknown vector through shifted argmax queries

1 vote
2 answers
57 views

Solve the recurrence $T(n)=T(n-2)+\frac{1}{\lg{n}}$

1 vote
2 answers
71 views

Union of non regular and regular language

0 votes
1 answer
85 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

3 votes
1 answer
83 views

How many random bits does this algorithm use on average?

1 vote
1 answer
83 views

Algorithm for optimal item selections

1 vote
1 answer
76 views

Number of decycling sets in a 3-regular planar graph

0 votes
2 answers
96 views

( Soft question ) P vs NP - is such a situation possible?

0 votes
1 answer
58 views

Can you compute a majority function of n-bits using an O(n) size circuit?

0 votes
1 answer
57 views

Is L={0^n 1^n ∣n≥0} context free language?

1 vote
1 answer
91 views

Maximizing sum and product of an array

0 votes
1 answer
55 views

Visiting all nodes of a directed graph exactly once (not dfs)

0 votes
0 answers
90 views

Finding all stable matchings in stable marriage problem

3 votes
1 answer
54 views

What is the complexity of minimising a convex quadratic function over the integers?

1 vote
1 answer
89 views

Is there an efficient algorithm for this ecommerce optimization problem?

1 vote
2 answers
87 views

NP-hardness of modified distance-colouring of graphs

-1 votes
1 answer
86 views

Create DFA such that every substring of w of length 3 contains two or three 0's with w={0,1}

1 vote
0 answers
85 views

Can we compute most significant digit of a binary number in O(1) on RAM model?

0 votes
3 answers
109 views

Testing whether a number (N) is prime or not can be made very fast but it will require storage space

1 vote
1 answer
63 views

Sorting rational numbers in linear time

0 votes
1 answer
47 views

How to modify Dijkstra's algorithm to model the path of an electric car?

2 votes
2 answers
36 views

Is loading from L2 or L3 of multi level cache direct or require a transfer to L1

1 vote
1 answer
59 views

If NP $\subset$ BPP, then NP $\subset$ RP. Confusion about the correctness of Probabilistic Turing Machine

0 votes
1 answer
58 views

$k$-way number contiguous partitioning

1 vote
2 answers
57 views

Complexity of satisfiability for relational logic on the booleans

0 votes
1 answer
57 views

Turing machine comparing two binary numbers in linear time

1 vote
1 answer
44 views

Expected maximum matching size in a random bipartite graphs

0 votes
1 answer
72 views

Formally Verify if a Sequence of Regex-Based Modifications is Idempotent

1 vote
1 answer
56 views

Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth

1 vote
2 answers
43 views

In the simulation of a C-program by a Turing machine, how does a TM determine which instruction to execute?

2 votes
1 answer
55 views

Dinitz’ algorithm in simple unit-capacity networks

0 votes
2 answers
69 views

How to find prefixes and suffixes for infinite languages? (Automata)

0 votes
0 answers
69 views

Is the following a correct proof for the interval covering problem?

1 vote
1 answer
52 views

If the Navier-Stokes equations problem is a computable problem, for example a set/language called "L", what are the elements of L?

3 votes
1 answer
31 views

Increasing families of expander graphs

2 votes
2 answers
51 views

Derivation trees to show a given grammar is ambiguous

2 votes
1 answer
51 views

Comparison of different algorithms for summing floating point numbers


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