# All Questions

6 views

### How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?

Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at ...
21 views

### Use of jackson structured program

Here is a question related to jackson structured program. I am very new to this concept. Can you please help me out by providing a solution to this question here. Q: ABC Company requires a tool to be ...
38 views

### Are there works on function complexity classes not included in FNP?

Are there book chapters on classes of function problems not contained in FNP? If not, are there research articles on this topic?
25 views

### Average number of sets given by greedy set cover? Is it uniform distribution?

We're covering the whole random universe $U$ of size $m$ with random sets $S_{1},\dots S_{n}$. I know that greedy set cover gives us a number between size of the minimal set cover and size of the ...
102 views

### Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand. In Diffie-Hellman Alice and Bob ...
93 views

### What is the application of combinatorial game theory

I find Combinatorial Game Theory very interesting as my primary interest is mathematics. My question is why do Computer Scientists (who tend to have a more practical approach) study it as well? Are ...
85 views

### Smallest possible universal combinator

I am looking for the smallest possible universal combinator, measured by the number of abstractions and applications required to specify such a combinator in the lambda calculus. Examples of universal ...
110 views

### Assignment problem with multiple workers for each job

I am wondering if there are any results on the following version of the assignment problem. We are given a set of jobs $J$ and a set of workers $W$, and for each job $j$ and worker $w$ we are given ...
51 views

### is every L in pspace-complete is nl hard? if yes then why? [on hold]

is every L in pspace-complete is nl hard? if yes then why? if not then why cant there be L that is pspace complete and in NL?
67 views

19 views

### References for family network studies

Is there any recent review/list of research articles/book on studies of family networks from the network science/theory point of view? I am studying network properties of family trees of a few ...
81 views

### Finding a random regular graph with degree d

I'm trying to find undirected random graphs $G(V,E)$ with $|V|$ = $d^2$ for $d \in \mathbb{N}$ such that $\forall v \in V: deg(v) = d$. For $d \in 2\mathbb{N} +1$ this trivially is impossible as no ...
31 views

### Estimate the cut edges in graph partitionining

Consider a large graph consisting of n nodes and e edges and an average degree of 2*e/n that is partitioned in k subgraphs such that the partitions are balanced, i.e. equal number of nodes at each ...
78 views

### Why are there only two bits? [on hold]

I was thinking that why are their only two bits,0&1. I know that they represent a particular switch in IC being opened or closed. But why not for switch neither completely open nor closed i.e. in ...
23 views

### Difference in complexity in checking the acceptance of a word vs finding an accepting word [on hold]

We know that the complexity of checking whether some word $w$ is accepted by a turing machine $TM$ is undecidable. But what about the complexity of finding one accepting word of a $TM$? Are these two ...
55 views

### “Elements of Information Theory”: Some (basic) help needed here

I was following the textbook by Cover & Thomas (2006): Elements of Information Theory. (hyperlink is not owned by me) I have one question that has been irking for me some time. It is regarding ...
134 views

### Is the nonnegativeness of a polynomial hard for $\mathsf{NP}_\mathbb{R}$?

It is clear that the following problem is in $\mathsf{NP}_\mathbb{R}$. Input: a list $P$ of triplets $(a,s,t)$ where $s$ and $t$ are nonnegative integers. Output: is there an $x\in \mathbb{R}$ such ...
78 views

### NP-hardness of a quadratic programming problem

Motivated by the mean-variance optimization, I came up with the following question: Given $n$ integers $a_1, \cdots, a_n$; $n$ lower bounds $0<\ell_1, \cdots, \ell_n<1$ $n$ upper bounds ...
61 views

### Finding all possible simple cyclic paths in a digraph

I have a strongly connected component with over 200 vertices and more than 600 edges. I need to iterate through each simple cycle in the graph exhaustively, without specifying a particular node. Is ...
167 views

### Does this problem related to subset sum have a name?

I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research. ...
87 views

### Lexicographic perturbation for euclidean shortest path instances?

Assume we have an undirected graph $G=(V,E)$ and vertex locations $\pi: V \rightarrow \mathbb{R}^2$. I am looking for a procedure to perturb the vertex positions to obtain new positions $\pi'$ such ...
72 views

### Polynomial Time Delay Enumeration of Maximal Bipartite Subgraphs

Let $G=(V, E)$ be an undirected simple graph. Is it known how to list all the maximal bipartite subgraphs of $G$, without repetitions, and with a polynomial time delay and a polynomial space ...
457 views

### Problems with no quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
67 views

### Complexity of eigenvaue problem

Many matrix diagonalization algorithms have time complexity $\mathcal{O}(n^3)$ where $n$ is the number of columns/raws (consider only square matrices). What is the best time lower bound it is known? ...
88 views

### If a problem is not in NP, does it have to be NP-hard [closed]

Is every non-NP problem NP-hard? In other words, does every problem in NP reduce (in polynomial time) to every problem outside of NP? Equivalently, does 3SAT (or your favorite other NP-complete ...
32 views

### Efficiently picking free position from array with uniform probability.

For each array position it is known if position filled or not. How efficiently pick one free position with uniform probability? That task happen during implementation of AI by Monter-Carlo method ...
Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ ...