## Top new questions this week:

### Prove that $n$ is a time-constructible function

I am reading Arora and Barak's book: "Computational Complexity: A Modern Approach". On page 16, the authors wrote: A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time constructible if ...

complexity-theory time-complexity turing-machines
 asked by Wei-Cheng Liu Score of 4

### Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...

algorithms mergesort
 asked by releseabe Score of 4
 answered by ratchet freak Score of 8

### Are these two definitions related to strong NP-hardness equivalent?

Let $P$ be a computational problem whose inputs are integers. Consider the following properties: (a) There exists a polynomial-time reduction from some strongly-NP-hard problem $Q$ to $P$. (b) $P$ is ...

reductions np-hard integers polynomial-time-reductions
 asked by Erel Segal-Halevi Score of 4
 answered by ttnick Score of 2

### Is 3, 3 satisfiability trivial after all?

Tovey's paper from 1982 clearly states that: Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable. ...

np-complete satisfiability
 asked by nonsensical world Score of 4
 answered by Noah Schweber Score of 8

### Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff

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 ...

data-structures binary-search-trees avl-trees
 asked by DaniDin Score of 3
 answered by Ashwin Ganesan Score of 6

### Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...

algorithms complexity-theory computability decision-problem
 asked by pabloealvarez Score of 3

I am trying to prove that $T(n)\in\Theta(n!)$ for the following recurrence using the master theorem: $\qquad T(n) = 16T\left(\frac{n}{4}\right)+ n!$ My attempt We have that $f(n) = n! \in \Omega(n^{\... time-complexity master-theorem  asked by z.. Score of 3  answered by Chenyang Score of 3 ## Greatest hits from previous weeks: ### Construct DFA accepting strings ending with '110' or '101' Let the alphabet be$\Sigma=\{0,1\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state. I have a solution with more ... automata finite-automata  asked by M.Usman Score of 2  answered by Yuval Filmus Score of 5 ### Longest path in an undirected tree with only one traversal There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex$v$and find the farthest vertex from it; say it is$v'$. ... algorithms graphs trees  asked by e_noether Score of 48  answered by Raphael Score of 25 ### What is the difference between user-level threads and kernel-level threads? After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference between ... operating-systems terminology concurrency os-kernel  asked by Sheldon Score of 34  answered by Gilles 'SO- stop being evil' Score of 30 ### Why is binary search faster than ternary search? Searching an array of$N$elements using binary search takes, in the worst case$\log_2 N$iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'... algorithms algorithm-analysis runtime-analysis search-algorithms binary-search  asked by The Mean Square Score of 60  answered by DCTLib Score of 87 ### How to prove greedy algorithm is correct I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ... algorithm-analysis proof-techniques correctness-proof greedy-algorithms  asked by D.W. Score of 50  answered by D.W. Score of 45 ### Mathematical benefit to use CPU/memory that increases by powers of 2 as 8-bit, 16-bit, 32-bit, 64-bit, etc? Historically, processors often increase in bit-size by powers of 2, such as 8-bit, then 16-bit, 32-bit, 64-bit. Although this has not always been the case, it is a well known trend. One benefit is ... cpu history  asked by BipedalJoe Score of 10  answered by Peter Cordes Score of 11 ### Absorption Law Proof by Algebra I'm struggling to understand the absorption law proof and I hope maybe you could help me out. The absorption law states that:$X + XY = X$Which is equivalent to$(X \cdot 1) + (XY) = X$No problem ... boolean-algebra  asked by user2635139 Score of 7  answered by Andrej Bauer Score of 10 ## Can you answer these questions? ### Stuck reading "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums" 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 ... lower-bounds  asked by Cecilia Chen Score of 1 ### Interactive Proof for Graphs with No Non-Trivial Automorphisms I am looking for an interactive proof for the language$AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}\$. I am interested in a method similar to the interactive ...

complexity-theory graph-isomorphism interactive-proof-systems
 asked by user171912 Score of 2
 answered by QuantumEnigma Score of 0

### Equivalence of two approaches for sparsity

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 ...

machine-learning neural-networks
 asked by Abhishek Tyagi Score of 1
You're receiving this message because you subscribed to the Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy

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

 <3