Top new questions this week:
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
|
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. ...
|
|
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|)$:
$...
|
|
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 ...
|
|
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 ...
|
Greatest hits from previous weeks:
|
|
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 ...
|
|
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?
...
|
|
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 ...
|
|
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, ...
|
|
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 ...
|
|
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 ...
|
|
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 ...
|
Can you answer these questions?
|
|
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.
...
|
|
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 ...
|
|
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, ...
|
