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

Explore our Questions

1 vote
1 answer
64 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

0 votes
1 answer
99 views

Comments on "Which combinatorial problem is similar to this problem?"

5 votes
1 answer
194 views

Weakest reduction for P-completeness

2 votes
1 answer
67 views

Exponential Time Hypothesis and the input size vs number of variables

22 votes
1 answer
2k views

Classification of intractable/tractable satisfiability problem variants

1 vote
2 answers
44 views

Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?

1 vote
0 answers
19 views

Showing that $ASPACE(f (n)) = DTIME(2^{O(f (n))})$

1 vote
1 answer
43 views

What would $P = NP$ tell us about how the polynomial hierarchy relates to $PSPACE$

3 votes
2 answers
280 views

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

1 vote
1 answer
54 views

Time Complexity of Exponentiation Operation as per RAM Model of Computation

2 votes
1 answer
34 views

Complexity of a restricted SAT problem

1 vote
1 answer
157 views

How to prove that one problem belongs to class P?

1 vote
1 answer
33 views

Sum in counting satisfying assignments

0 votes
2 answers
371 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

Browse more Questions