Theoretical Computer Science Stack Exchange Community Digest

Top new questions this week:

Recent advances in computer science since 2010?

Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example, Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...

ds.algorithms soft-question  
user avatar asked by user12344567 Score of 52
user avatar answered by Martin Berger Score of 29

What are the consequences of $BPP \neq P$?

I have seen a lot of people assume, $BPP = P$ . But to me, this seems false intuitively.(Though math is not without unintuitive results) And, to my admittedly limited understanding of the topic, the ...

polynomial-time derandomization probabilistic-computation  
user avatar asked by Colonizor48 Score of 5
user avatar answered by Timothy Chow Score of 5

Could a quantum computer prove theorems with infeasibly long proofs?

The mathematician Andrew Granville recently published a "philosophical" article, Accepted proofs: Objective truth, or culturally robust?. At the end, he mentions in passing a suggestion by ...

quantum-computing proof-theory  
user avatar asked by Timothy Chow Score of 5

Assignment problem for forming pairs of real numbers

Suppose I have two sets of real numbers, $X$ and $Y$, each of cardinality $N$. I would like to assign these points to pairs $(X_i, Y_j)$ such that the sum of squared intra-pair distances is minimized. ...

user avatar asked by user1248163264 Score of 3
user avatar answered by D.W. Score of 3

Fast algorithms for time bounded Kolmogorov complexity

For a universal Turing machine $U$, the time bounded Kolmogorov complexity of a string $x$ is silmilar to the usual Kolmogorov complexity but limited to programs $p$ running in time at most $t(|x|)$: $...

time-complexity turing-machines polynomial-time kolmogorov-complexity  
user avatar asked by agemO Score of 3

is SUBEXP contained within PSPACE?, NP?

Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...

time-complexity np complexity pspace  
user avatar asked by Colonizor48 Score of 3

FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge ...

graph-algorithms approximation-algorithms counting-complexity approximation-hardness  
user avatar asked by a3nm Score of 2

Greatest hits from previous weeks:

Finding the shortest path in the presence of negative cycles

Given a directed cyclic graph where the weight of each edge may be negative the concept of a "shortest path" only makes sense if there are no negative cycles, and in that case you can apply the ...

ds.algorithms graph-algorithms shortest-path  
user avatar asked by jleahy Score of 15
user avatar answered by BlueRaja - Danny Pflughoeft Score of 28

Explain P = NP problem to 10 year old

It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it? ...

cc.complexity-theory soft-question teaching p-vs-np  
user avatar asked by Mohsin Hijazee Score of 56
user avatar answered by Geoffrey De Smet Score of 36

Why would one ever use an Octree over a KD-tree?

I have some experience in scientific computing, and have extensively used kd-trees for BSP (binary space partitioning) applications. I have recently become rather more familiar with octrees, a similar ... tree  
user avatar asked by Noldorin Score of 44
user avatar answered by David Eppstein Score of 30

Theoretical Computer Science vs other Sciences?

So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...

cc.complexity-theory lo.logic fl.formal-languages automata-theory  
user avatar asked by voltas1231 Score of 11
user avatar answered by Andrej Bauer Score of 25

A simple decision problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...

computability decidability  
user avatar asked by Lev Reyzin Score of 102
user avatar answered by Scott Aaronson Score of 104

What's new in purely functional data structures since Okasaki?

Since Chris Okasaki's 1998 book "Purely functional data structures", I haven't seen too many new exciting purely functional data structures appear; I can name just a few: IntMap (also invented by ...

reference-request big-list functional-programming  
user avatar asked by jkff Score of 616
user avatar answered by jbapple Score of 601

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two arbitrary ...

cr.crypto-security hash-function  
user avatar asked by Thomas Owens Score of 31
user avatar answered by Ross Snider Score of 33

Can you answer these questions?

What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...

cc.complexity-theory complexity-classes pspace  
user avatar asked by Nift Score of 1

Elimination of monadic second-order quantifiers

I'm trying to understand what is currently known to be possible regarding the elimination of monadic second-order quantifiers. Many sources cite that monadic second-order logic supports elimination of ...

user avatar asked by gigabytes Score of 1

Equivalence between GNFA and NFA/DFA

In Section 1.3 of the 3rd edition of Michael Sipser’s Introduction to the Theory of Computation, it is proven that regular expressions are equivalent to deterministic finite automatas (DFAs). That is, ...

fl.formal-languages automata-theory  
user avatar asked by Abced Decba Score of 1
You're receiving this message because you subscribed to the Theoretical Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 14 Wall Street, 20th Floor, New York, NY 10005