Top new questions this week:
|
|
There is a naive semidecision algorithm for the halting problem: simply simulate the program and see if it halts. Is there an algorithm that is asymptotically faster? More precisely, suppose the naive ...
|
|
For a given undirected graph $G$ , let $ c(G) $ denote the length of the longest cycle in $ G $ (by cycle, we mean a closed path without repetitions). Prove that if there exists a polynomial-time ...
|
|
I am reading the paper titled "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums", and I am stuck on theorem 2.1, I believe it is wrong, the proof has a wrong ...
|
|
Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...
|
|
For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
|
|
Problem: A set of formulas $M_0$ is an axiom system for a set of formulas $M$ if $\{A |A \text{ is a model for }M_0\} = \{A |A \text{ is a model for }M\}$, where $A$ is an assignment, or valuation. $M$...
|
|
Suppose we have $n$ boolean variables, $x_1, \dots, x_n$. Some boolean variables can have implication relationships, e.g. $x_2 \implies x_5$, which means that if $x_2$ is true $x_5$ must also be true. ...
|
Greatest hits from previous weeks:
|
|
I am finding it difficult to clearly differentiate between Multiprogramming and Multitasking.
My primary source has been Wikipedia, but the WP article seems to be a little at odds with some less ...
|
|
Why do we use other bases which are neither binary (for computers) nor decimals (for humans)?
Computers end up representing them in binary, and humans strongly prefer getting their decimal ...
|
|
I've always wondered why processors stopped at 32 registers. It's by far the fastest piece of the machine, why not just make bigger processors with more registers? Wouldn't that mean less going to the ...
|
|
Are all Morse code strings uniquely decipherable? Without the spaces,
......-...-..---.-----.-..-..-..
could be Hello World ...
|
|
As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not ...
|
|
I know the term order of a B-tree. Recently I heard a new term: B tree with minimum degree of 2.
We know that the degree is related to a node but what is the degree of a tree?
Does degree impose any ...
|
|
I've read what a Turing machine and a UTM are, but I don't get the difference. What can a UTM do which a normal Turing machine can not?
|
Can you answer these questions?
|
|
I am trying to understand whether the following two ways to achieve a sparse matrix are equivalent in Pytorch. Let me add some context:
I am training Sparse Neural Networks with a specific structured ...
|
|
Let $R$ be the set of all decidable languages. Consider $P^R$. That is, the set of all languages that can be decided via a polynomial time deterministic TM with an oracle to any language $L\in R$.
I'd ...
|
|
Over the years I've worked on a few applications that needed to model time intervals that are disjoint. For example, there's some kind of equipment available and time slots are booked out. For a data ...
|
