0
votes
0answers
2 views

How are new probabilities computed when simulating measurement on a set of qubits?

Suppose I have a set of 3 qubits and I have calculated the probabilities for their distribution: |000> -> a |001> -> b |010> -> c |011> -> d |100> -> e |101> -> f |110> -> g |111> -> h With it ...
-1
votes
0answers
11 views

convex hull of projections

$\newcommand{\convh}{\text{convh}}$Suppose that two convex polytopes $Q,S\in \mathbb{R}^n$ are given, where $Q= \convh(\bigcup_{a=1}^t Q_a)$ and $S= \convh(\bigcup_{b=1}^r S_b)$ where the $Q_a$'s and $...
0
votes
0answers
31 views

Testing for satisfiability of a system of linear equations over GF(2)

Consider a system linear equations in $x$, $Ax =b$, where A is an $n\times n$ matrix, and $b$ is a column vector, and all operations are over $GF(2)$. Is it easier to check satisfiability of the ...
4
votes
1answer
59 views

How do you get the Calculus of Constructions from the other points in the Lambda Cube?

The CoC is said to be the culmination of all three dimensions of the Lambda Cube. This isn't apparent to me at all. I think I understand the individual dimensions, and the combination of any two seems ...
4
votes
2answers
48 views

Known and described subclasses of Context-Free Grammars class

I'm looking for various researches which consider specific subclasses of Context-Free Grammar class, i.e. some specific described cases, which differ from well-known: deterministic/non-deterministic ...
-2
votes
0answers
29 views

a linear sort program? [on hold]

I want to know the goal of the following question taken from my text book: Suppose its known that each of the items in $a\space[1.\space.N]$ has one of two distinct values. Give a sorting method ...
-3
votes
0answers
76 views

what if P = NP intersection CO-NP [on hold]

Can someone tells what if p equals np intersection co-np. I am sorry i cannot write the qeustion in popper notations cause i dont know how to do that thanks
0
votes
0answers
28 views

What are the connections between P-complete and L-complete [on hold]

I have limited knowledge about complexity theory. From what I learned, DFA membership testing is an L-complete problem. However, I am not quite sure what it implies. For example, is it also a P-...
4
votes
1answer
71 views

“Impredicative” in type theory

I am confused. I think I've read two usages of the word "impredicative" in type theory: When people talk about the "impredicative" version of Martin-Löf's type theory, which they say it is ...
0
votes
0answers
42 views

On the size of residue classes

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$ ...
5
votes
0answers
127 views

MLTT vs. [weak] MSOL

I've noted that both Martin-Lof type theory and [Weak] Monadic Second-Order logic (eg over trees) enjoy the ability to express basically any finite computer program, in a decidable manner. I was ...
1
vote
1answer
137 views

Structured set of binary words

Definitions: Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$. For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that: Every element $e$ ...
1
vote
0answers
28 views

Cluster Edge Deletion on 2-trees

Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced ...
-1
votes
0answers
26 views

How to interpret these adiabatic evolutions?

I was trying to study the adiabatic Hamiltonian defined in the paper (arXiv:1207.1712) titled 'Solving the Graph Isomorphism Problem with a Quantum Annealer'. My case is the cycle graph $C_n$ when $n$...
4
votes
1answer
91 views

Kth best problem that is NP-hard for K polynomial

A Kth best problem is, given some constraint, to find a solution that has the Kth best value compared to all solutions that meet the constraint. One way to write this as a decision problem is to ...
-2
votes
1answer
74 views

Finding All Cliques of an Undirected Graph

How can I list all cliques of an Undirected Graph ? (Not all maximal cliques, like the Bron-Kerbosch algorithm)
4
votes
2answers
114 views

Characterisation of P in terms of register machines

It is a well-known result that Turing machines and random access machines (RAMs) can simulate each other with a polynomial slowdown. It is relatively straightforward to prove that indirect addressing ...
3
votes
0answers
68 views

Communication complexity protocols depending on inputs

Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to ...
-1
votes
0answers
19 views

Reference Request : Computing directed domination number of Oriented graphs

An oriented graph ($\overrightarrow{G}$) is a directed graph having no symmetric pair of directed edges (arcs). A directed dominating set in a directed graph $D$ is a subset $S$ of vertex set $V$ ...
0
votes
1answer
42 views

Efficient update of reachable set of a node in a digraph

Given a digraph $G = (V, E)$ and a set of vertices $S$, which does not change over the whole process, the goal is to compute the set of vertices, $R_{reach}$, reachable from $S$ and the set of nodes , ...
-4
votes
1answer
90 views

What is the relationship between tail recursion with other recursions? [on hold]

I'm rather confused by the recursion theory. From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But ...
-6
votes
0answers
24 views

Asking for DFA Problem Solution [closed]

Help me to find out the solution, Give a DFA for Σ = {a, b} that accepts strings with ( ab U aba )*
-1
votes
1answer
88 views

how to show that there is no derivation in system type [closed]

look at my system type (rules of them): $$\frac{\Gamma(x:\tau)\vdash e:\rho}{\Gamma(x:\tau)\vdash \lambda x .e:\tau\rightarrow\rho}$$ $$\frac{\Gamma\vdash e_1:\tau\rightarrow\rho\ \ \ \ \ \Gamma\vdash ...
1
vote
0answers
30 views

How does the simplified Stabilizer ZX Calculus limit the Quantum Algorithms expressable?

In response to a series of papers demonstrating that the ZX calculus was complete for Stabilizer Quantum Mechanics but not universal Quantum Mechanics, a Stabilizer ZX Calculus was proposed (http://...
17
votes
2answers
271 views

Deciding whether a unary context-sensitive language is regular

It is a well-known result that the question Does a context-free grammar generate a regular language? is undecidable. However, it becomes decidable on a unary alphabet, simply because in this ...
1
vote
0answers
46 views

Path finding on graph with state dependent edge costs

I'm looking for a version of path planning that is able to find paths in a graph where edge costs depend on the state of the moving entity. In such cases, it is required to also consider trade-offs, i....
3
votes
1answer
115 views

Median finding with “green forests”?

I have a vague memory of a series of papers working to reduce the constant factor in the number of comparisons for deterministic linear time median finding, using increasingly elaborate (but ...
4
votes
0answers
117 views

P/Poly vs Uniform Complexity Classes

It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization. What is the smallest uniform class C for which one ...
0
votes
0answers
56 views

Approximating circuits with polynomial of low degree, can't understand small detail in the proof

I'm looking at the proof of this lemma: Lemma For every integer $t>0$, there exists a (proper) polynomial of total degree $(2t)^d$ that differs with $C$ on at most $size(C) 2^{n-t}$ inputs Where ...
2
votes
1answer
67 views

What is the recognition complexity of k-uniform k-partite hypergraphs? [duplicate]

We can easily recognize bipartite graphs, but I surprisingly couldn't find anything on the recognition complexity of 3-uniform tripartite hypergraphs, though I'm sure this has been studied. It's also ...
5
votes
1answer
91 views

Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at ...
7
votes
1answer
190 views

NP-hardness on Cayley graphs

What is known about complexity of NP-hard problems on Cayley graphs? Suppose that the graph is given explicitly as the multiplication table of the group and the list of generators. So the input ...
4
votes
4answers
180 views

Find the maximum subset contained by a ball of radius R

I am searching for the name of / literature to the algorithmic problem as follows: Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$,...
0
votes
0answers
48 views

How much variance is captured by the RFF maps? [migrated]

The RFF maps here are possibly the most used feature maps. I was wondering if there are cases where anyone has theoretically estimated the total variance captured by these maps? Is any simplification ...
1
vote
1answer
99 views

What's the effect of imposing the following restriction on inductive type families?

Let a simple expression be either: A free variable A data constructor of an inductive type family, applied to 0 or more simple expressions What would be the effect of imposing the following ...
0
votes
1answer
44 views

What are the general classes of measured systems

Imagine there is a class of system such that a measurement can be performed on an exemplar of this class, each measurement producing 1 bit of information. There are no limitation on how many times the ...
1
vote
0answers
73 views

Distribution attaining minimum discrepancy of disjointness function

Is it true that for the optimal distribution $\nu$ (not necessarily uniform) that attains minimum discrepancy $\mathsf{disc}(\mathsf{DISJ}_n)$ for the disjointness function $\mathsf{DISJ}_n$ we have ...
8
votes
1answer
107 views

Pathwidth of planarized drawing of $K_{3,n}$

The pathwidth of the complete bipartite graph $K_{3,n}$ with partite sets of size $3$ and $n$ is at most $3$. I am interested in planarizing this graph by the following process: Draw it in the ...
-2
votes
0answers
190 views

Efficient algorithm for testing planarity of the union of two planar graphs

Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs. Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar? That is, an algorithm more efficient than ...
0
votes
1answer
67 views

Convergence and representation theorems for machine learning

I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology. Let's say we have a function $...
-1
votes
1answer
113 views

Paritioning a graph into clique and independent set

I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...

15 30 50 per page