Problem Detail: Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem? Do we know its complexity? Read More …
Blog
[Solved]: Conceptual question about entropy and information
Problem Detail: Shannon’s entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that we are more uncertain about what will happen next. What Read More …
[Solved]: Is it admited to give the complexity of a function regarding the resulting data structure?
Problem Detail: Assume that we have a data structure which uses $O(log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$. The time complexity of $f$ is $O(n_{_{old}})$ Read More …
[Solved]: Maximal difference of height between two leaves in an AVL tree
Problem Detail: What is the maximal difference between heights of leaves in an AVL tree? I am interested only in the asymptotic difference. I am not sure about my answer – I think that it is $O(log n)$, given the fact Read More …
[Solved]: Which theoretical parallel model is closest to CUDA?
Problem Detail: Which theoretical parallel model is closest to CUDA/OpenCL programming model? For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too generic, since it makes abstraction of various memory access Read More …
[Solved]: Can a language have $Sigma^{*}$ as its syntactic monoid?
Problem Detail: As per the title I was wondering if it’s possible for a language $L subseteq Sigma^{*}$ to have $Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that Read More …
[Solved]: If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Problem Detail: Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro et al. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, if someone shows s that UNIQUE Read More …
[Solved]: Depth-2 circuits with OR and MOD gates are not universal?
Problem Detail: It is well-known that every boolean function $f:{0,1}^nto {0,1}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate Read More …
[Solved]: Can we understand SVM without knowledge of Machine Learning
Problem Detail: I was told by my adviser (future one) to look into libsvm library or any other and try to get familiar with it.. to work on a programming project (on Machine Learning) (will start in a month). my background: Read More …
[Solved]: NP-complete reductions
Problem Detail: I’ve read that “Every problem in NP can be reduced to every NP-complete problem”. My question is on the choice of the word “reduce”. If I were to “reduce” a polynomial problem in NP to an exponential problem in Read More …
