Most Popular
1500 questions
30
votes
4 answers
Implications of unprovability of $P\neq NP$
I was reading "Is P Versus NP Formally Independent?" but I got puzzled.
It is widely believed in complexity theory that $\mathsf{P} \neq \mathsf{NP}$. My question is about what if this is not provable (say in $ZFC$). (Let's assume that we only find…
karthik
- 417
- 4
- 9
29
votes
2 answers
Ladner's Theorem vs. Schaefer's Theorem
While reading the article "Is it Time to Declare Victory in Counting Complexity?" over at the "Godel's Lost Letter and P=NP" blog, they mentioned the dichotomy for CSP's. After some link following, googling and wikipeding, I came across Ladner's…
user834
- 2,806
- 21
- 27
29
votes
1 answer
Toy examples for barriers to $P \ne NP$
Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?
v s
- 2,208
- 13
- 21
29
votes
1 answer
Why are regular languages called "regular"?
Why are regular languages (and from that regular expressions) called "regular"? There is lot of regularity also in context-free languages other types of languages.
I suppose that, in the beginning, the adjective "regular" has been used to…
gioele
- 397
- 1
- 3
- 8
29
votes
8 answers
What is the minimum number of bits required to store a sudoku puzzle?
Note: This is about the standard 9x9 sudoku puzzle. The solution only has to support solved, legal puzzles. So a solution doesn't need to support empty cells and can rely on the properties of a solved sudoku puzzle.
I was wondering this, but I…
orlp
- 885
- 6
- 13
29
votes
2 answers
How many DFAs accept two given strings?
Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected, minimal, or non-degenerate ones); thus,…
Aryeh
- 10,494
- 1
- 27
- 51
29
votes
2 answers
How to publish a paper?
Being a software engineer for the most part of my life I have absolutley no idea how to start with publishing an "academic" kind of paper. During my latest research I've found an interesting algorithm for the task I've been solving (related to some…
lithuak
- 551
- 4
- 7
29
votes
1 answer
Inductive types for large countable ordinal notations.
I'm looking to build notations for large countable ordinals in a "natural way". By "natural way" I mean that given an inductive data type X, that equality should be the usual recursive equality (the same that deriving Eq in Haskell would produce)…
Russell O'Connor
- 618
- 4
- 7
29
votes
10 answers
Current parallel models for computation
The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.
Are these areas still active in terms of research for parallel algorithms? Are there newer…
Nicholas Mancuso
- 746
- 7
- 15
29
votes
4 answers
Proofs obtained only through spectral graph theory
I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.
However, I'm curious about a statement that popped up in…
Anthony Labarre
- 3,264
- 1
- 25
- 33
29
votes
6 answers
Are there NP-complete problems with polynomial expected time solutions?
Are there any NP-complete problems for which an algorithm is known that the expected running time is polynomial (for some sensible distribution over the instances)?
If not, are there problems for which the existence of such an algorithm has been…
Steve Kroon
- 393
- 3
- 5
29
votes
4 answers
Compendium of the Best Approximation and Hardness Results for NP optimization problems
Do you know any up-to-date wiki dedicated to NP optimization problems with their best approximation and hardness result?
Based on the feedback, it seems that it is safe to assume there is not such a resource (see the end of this question for two…
randomizer
- 741
- 5
- 15
29
votes
1 answer
Are there any public synchronous discussion forums (slack, discord, etc.) for TCS
I'm a 2nd year masters student studying theoretical CS (algorithms to be precise). I would like to know if there are any public synchronous discussion groups (slack, discord, etc.) for TCS. CSTheory StackExchange works well when someone has a…
Bhishmaraj
- 401
- 3
- 10
29
votes
3 answers
Presenting work-in-progress (slides now available)
Presentation now given. Slides available below.
Presenting work-in-progress is something we all should do in order to obtain early feedback and to help crystallize our ideas. Unfortunately, many graduate students need help getting over this hurdle…
Dave Clarke
- 16,666
- 3
- 60
- 106
29
votes
6 answers
Which SAT problems are easy?
What are "easy regions" for satisfiability? In other words, sufficient conditions for some SAT solver to be able to find a satisfying assignment, assuming it exists.
One example is when each clause shares variables with few other clauses, due to…
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39