# All Questions

2 views

### Is Kolmogorov complexity quasi-surjective?

For Kolmogorov complexities $\hspace{.02 in}K$ induced by essentially-optimal description languages, does there exist an integer $c$ such that for all positive integers $n$, there exists a string ...
9 views

### Binary tree - linking nodes - complexity

In binary tree each node has: 2 pointers for sons(as usual), value and additional pointer(which at the begining points at nothing) - let's call it 'link'. Change value of 'link' in each node to point ...
47 views

### $A,B \in P \Rightarrow A \leq_p B$ [on hold]

"Complexity theory" is new to me. Today "polynomial-time reduction" was introduced and now I'm asking myself if the following is correct: $A,B \in P \Rightarrow A \leq_p B$ It might be simple, but ...
28 views

### Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
282 views

### Is the following problem in P or in NP?

Given an integer $K$, a set of tasks $T=\{a_1,b_1,\dots,a_n,b_n\}$ with sequence dependent execution times $E:T \times T \rightarrow \mathbb{N}$ and precedence constraints on $T$ of the following ...
28 views

### DAG reduce edges by transitivity

I have a DAG like this $G_1 = \lbrace A \to B \to C \rbrace$ My algorithm modify $G_1$ so it will be like this $G_2 = \lbrace A \to C, B \to C \rbrace$ I now that $G_2$ is not a transitive ...
49 views

### EXP-Complete oracle separating P and NP

Is there an $EXP-Complete$ oracle B which satisfies $P^B\neq NP^B$. Right now the only language $B$ i know which satisfies $P^B\neq NP^B$ is the one appearing in chapter 3 of "Computational ...
13 views

### minimum energy broadcasting in wireless networks references request

I am currently doing a survey on "Minimum energy broadcasting in wireless networks". I am specifically looking into heuristics like Broadcast Incremental Power algorithm and its variants. Please ...
36 views

### In domination perfect graphs is MDS certificate for MIDS?

I suspect this is wrong in case it makes sense at all. According to graphclasses: A graph is domination perfect if for every induced subgraph $H$ a minimum dominating set (MDS) has the same ...
25 views

### Big O notation for vectors - basic algorithm [on hold]

I would like to insert data from one vector to another if its element satisfies some conditions My algorithm is like this ...
50 views

### Number of ways to extend almost independent sets of graph

Given $G$ a regular graph on $n$ vertices denote $\alpha(G)>1$ to be independence number. Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality ...
41 views

### On notion of positive rank

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
29 views

### Persistent data structures in RAM computational model

Always when I read about any efficient persistent data structures they use pointer computational model. I'm wondering if you know any efficient implementation which uses power of RAM model?
24 views

### Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
27 views

### Understanding Frieze's log(n) approximation algorithm for ATSP

In the Frieze's log$_{2}$(n) approximation algorithm for ATSP, let's consider any $G_{o}$ $\subset$ G, where G is the underlying complete digraph with n vertices, CYC(G$_{o}$) be the cost of optimal ...
89 views

### The relationship between completeness and strength of reductions

Ladner theorem can be stated as: $P \ne NP$ if and only if there exists an incomplete set in $NP-P$. Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time ...
79 views

65 views

### What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?

My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, ...
51 views

### Implications of a deterministic polytime prime-finding algorithm

I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem: Given $n$ in binary, output a prime $p > n$. I'm both curious about ...
52 views

### Learning k-parities with Membership Queries and Persistent Noise

Random independent misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by ...
137 views

### Array-like data structure with O(1) worst-case concatenate/join?

I am looking for a data structure $D$ which supports the following operations (preferably a (binary) tree-like structure): $D$ is indexed, i.e. there is a mapping from $\{1, \ldots, n\}$ to items ...
60 views

### Simple example of halting-unprovable Turing machine

Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system? Specifically, I'm curious whether ...
168 views

### What is the complexity of the equivalence problem for read-once decision trees?

A read-once decision tree is defined as follows: $True$ and $False$ are read-once decision trees. If $A$ and $B$ are read-once decision trees and $x$ is a variable not occurring in $A$ and $B$, ...
34 views

### Finding exact value with a quotients of products of random values

Sorry for the haphazard title: really not sure what this should be called Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime). ...
31 views

### reported cases of pseudo random number generator biasing results

occasionally students ask about the theory of (pseudo) random number generators. it occurred to me it would be helpful to know significant reported cases where "not random enough" PRNGs were found to ...
40 views

34 views

### Computational complexity of Initial Value Problems of ODEs

Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
42 views

### Array partitioning with limitations on partition size

Consider an array of bytes. I want to partition the array, such that the following two conditions hold: The number of bytes within each partition (except perhaps the last one) is between L and U, ...
128 views

### Integer factorization using polynomial whose roots are prime factors

Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$ be the prime factorization of $n$ into $k$ distinct primes $p_{i}$. For such $n$, define ...
121 views

### Efficient generation of permutational invariant quantum states

Starting from $|00\cdots 0\rangle$, can permutational invariant quantum states, i.e. the following one:  |\psi_n\rangle = \frac1{n!} \sum \prod_{\pi\in S_n} ...
101 views

### Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. ...
82 views

### Is there a name for this Assignment definition

The standard Assignment Problem asks for an optimal one-to-one assignment between agents and tasks. Now consider the following generalization: Instead of specifying a cost of a single agent-task ...
21 views

### what's “pseudo time” when used in comparison with semaphores

I'm currently listening to Alan Kays' talk "Is it really complex or did we just make it complicated ?" (https://www.youtube.com/watch?v=ubaX1Smg6pY&= ) where he says that "semaphores were a bad ...
Given a graph $G$ and a proper vertex coloring $C$ with the minimum numbers of colors, how much faster can a maximum clique be found than when just $G$ is given? Additional information doesn't make ...