0
votes
0answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
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 ...
2
votes
1answer
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. ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
1
vote
0answers
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 ...
-2
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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$, ...
2
votes
1answer
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?
3
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
9
votes
2answers
79 views

Vector Addition Systems with finite “obstacles”

A Vector Addition System (VAS) is a finite set of actions $A \subset \mathbb{Z}^d$. $\mathbb{N}^d$ is the set of markings. A run is a non-empty word of markings $m_0 m_1\dots m_n$ s.t. $\forall i \in ...
4
votes
2answers
289 views

Weird claim of graphclasses about complexity of domination

EDIT this got 'fixed' on graphclasses, as per answers/comments, so you might not reproduce it, unless you have their earlier database, which is publicly available via sage - http://sagemath.org. ...
4
votes
0answers
100 views

Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
2
votes
0answers
49 views

$\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems

All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ ...
4
votes
0answers
83 views

Complexity of coloring in weakly perfect graphs?

A graph is weakly perfect if the clique number equals the chromatic number, i.e. $\omega(G)=\chi(G)$. Deciding membership is NP-complete according to the paper. Because of the inequality $\omega(G) ...
3
votes
1answer
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, ...
2
votes
0answers
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 ...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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 ...
10
votes
2answers
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$, ...
0
votes
0answers
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). ...
0
votes
0answers
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 ...
-1
votes
0answers
40 views

NP-hard problems [on hold]

I have two problems : Independent Set and SAT-3CNF. I've already shown that it's possible to reduce SAT-3CNF to Independent Set For example having $ (x_1 \lor \overline{x_2} \lor x_3) \land ...
0
votes
0answers
17 views

Compact encoding of sudoku puzzles [migrated]

I just "renewed" my password after a two-year absence (Jan. 2013). I answered the question re "minimum number of bits require to store a Sudoku puzzle" by describing a program implementation. I have ...
1
vote
0answers
37 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness ...
1
vote
1answer
60 views

How are random numbers structure-less?

I'm using random numbers for simulations. The main reason is to have an input sequence where no (simulation) algorithm is going to lock on a pattern and introduce unwanted effects into the simulation. ...
7
votes
1answer
122 views

Reference for the fact that (0=1) implies false requires a universe in MLTT

It's a fairly well-known fact that deriving a contradiction from a disequality (for example, $(0=1) \to \bot$) in Martin-Loef type theory requires a universe. The proof is also fairly ...
0
votes
0answers
16 views

Special case of k-ary labeled trees

Classical definition of k-ary labeled trees doesn't restrict somehow the uniqueness of tree labels inside its branches. My question: Is any special definition (name) for such trees? To clarify what ...
1
vote
1answer
32 views

A Question on Convex Conjugate Duality for KL Divergence

The convex conjugate of a function, say, $f:X\mapsto \mathbb{R}$ is a function $f^*:X^*\mapsto \mathbb{R}$ defined as $$f^*(x^*):=\sup_{x\in X} ~\langle x, x^*\rangle-f(x),$$ where $X^*$ is the ...
1
vote
1answer
135 views

Kolmogorov Complexity vs Running Time (Edited)

Let $U$ be a universal Turing Machine. Suppose I have a Kolmogorov incompressible string $s$ of length $n$. Let $A:\{1,...,n\} \to \{0,1\}$ be an algorithm such that $A(i) = s_i$. I believe that the ...
2
votes
1answer
95 views

Real representation versus communication complexity

Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for ...
4
votes
1answer
100 views

Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least ...
4
votes
1answer
135 views

On the notion of positive rank of a matrix

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$, ...
6
votes
0answers
93 views
+50

Are highly symmetric inequalities solvable over integers?

Suppose I have $n$ variables $x_1,\ldots,x_n$ that satisfy some inequalities that are highly symmetric, e.g., for all $S\subset [n], |S|=k$ we have $\sum_{i\in S} f(x_i,k)\le \sum_{i\in [n]} ...
1
vote
0answers
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 ...
1
vote
0answers
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, ...
6
votes
1answer
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 ...
3
votes
1answer
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} ...
1
vote
0answers
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$. ...
2
votes
1answer
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 ...
2
votes
0answers
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 ...
2
votes
0answers
119 views

How much faster is solving Clique in properly colored graph?

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 ...
1
vote
0answers
85 views

Example of non-disk bounding planarly nested sequences of cycles

I am trying to find an example for the Theorem 5.1 of the paper "Combinatorial Local Planarity and the Width of Graph Embeddings" that can be found at ...

15 30 50 per page