-1
votes
0answers
11 views

Directed Acyclic Graph with multi-parent nodes

Given: A directed acyclic graph with weighted edges, where a node can have multiple parents. Problem: For each child of root node, find a minimum-cost(sum of weights) path from such a child to some ...
0
votes
0answers
30 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
-1
votes
0answers
8 views

Visible point in simple polygon

A simple polygon $P$ is given. Prove the the point $q$ is internal point of the simple polygon $P$ if and only if each vertex $v$ of $P$ is visible from the point $q$. The first step is pretty much ...
7
votes
2answers
208 views

Complexity of solving linear equations

What is known about the complexity of solving a system of linear equations over some finite field? I know that there exists an $O(n^3)$ algorithm (Gauss) that computes a solution and that for sparse ...
-3
votes
0answers
18 views

Solving Recurrences

This is the recursion available \ \begin{equation} R_{n}=\frac{1}{n} \{C_1* R_{n-1} +C_2 * R_{n-2}\}, R_0 = A_0 ,R_1 = A_1 \end{equation} Given conditions $A_0,A_1,C_1,C_2 $ are constant ...
-2
votes
0answers
14 views

Tree Traversal - Simple Puzzle type Issue

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
1
vote
0answers
113 views

Theorem prover fails to find simple set theory proof?

I am trying to use an automated theorem prover (SNARK), to prove the following goal, from the following assertions (in first-order logic) - Assertions - The relation ‘part of’ is transitive. The ...
-2
votes
1answer
55 views

Prerequisites for theoretical computer science

I am a freshman and a Computer Science major,I have a very poor understanding in the area of electrical and electronics.I want to pursue a career in theoretical computer science esp. Quantum ...
0
votes
1answer
68 views

Which formalism is best suited for automated theorem proving in set theory?

Abbreviations - FOL is first-order logic; NBG is Von Neumann–Bernays–Gödel set theory; SEP is Stanford Encyclopedia of Philosophy; HOL is higher-order logic; ATP is automated theorem proving. Context ...
1
vote
0answers
35 views
+50

Automatically Adapting Forgetting Factor for Online EM

I've been reading some interesting papers recently on methods for automatically and adaptively setting the learning rate in stochastic gradient descent (SGD). In particular, "No more pesky learning ...
0
votes
0answers
24 views

Any examples of the following error detecting code?

A 2k-bit input is split into two k-bit halves, one half is chosen at random to be transmitted in the clear. The other half is encoded with the first half to produce a code, called X, of length 2k-1 ...
1
vote
1answer
166 views

Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments ...
0
votes
0answers
38 views

On a property of random rooted trees with $n$ nodes and of height $h$

I am working on a proof that require the result of the following problem: Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of ...
0
votes
0answers
35 views

Turing degree of computing definable reals [on hold]

We know that definable real numbers in general are not computable. So what would be turing degree of computing definable real numbers? Would every incomputable definable reals share same turing ...
0
votes
0answers
29 views

Estimating Graph/ Network Accuracy

If I'm creating a (social) network using some automatic system, which I know is not 100% accurate but for which I can estimate the rate of error, what, if anything, can I say about the accuracy of the ...
2
votes
2answers
58 views

How to translate the axiom schema of induction by Curry-Howard?

I'm trying to understand the Curry-Howard correspondence. I am comfortable with it for propositional logic, but get confused when $\forall, \exists$ quantifiers come in the picture. The axiom schema ...
-4
votes
0answers
27 views

Vanishing gradient in RNNs - yes or no? [on hold]

One of the often cited issues in RNN training is the vanishing gradient problem (Y.Bengio et al. doi:10.1109/72.279181), (S.Hochreiter doi:10.1142/S0218488598000094), S.Hochreiter et al., (R.Pascanu ...
6
votes
1answer
124 views

Is generalized pigeonhole search known to be no harder than PPP?

Consider the TFNP search problem Given a positive integer $t$ in unary, positive integers $M$ and $N$ (in binary), and a function from $\{0\hspace{.02 in},\hspace{-0.04 in}1,\hspace{-0.03 ...
6
votes
3answers
759 views

Are there any cases where quantum has given insight for classical algorithms?

To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum ...
-7
votes
0answers
36 views

What did Turing call Turing Machines?

I hope he didn't go with the uninspired "Turing Machines."
3
votes
0answers
65 views

extracting/ exploiting similarity of SAT instances by solver

suppose that two SAT formulas on different variables $F_1, F_2$ are given on the input that are known to be true and the problem is to build an algorithm that finds a solution to each. the formulas ...
5
votes
1answer
53 views

Is any QMA-intermediate problem known?

Similar to the class of classical NP-intermediate problems (e.g. Graph Isomorphism), is there any "QMA-intermediate" problem known, that is in QMA but not known to be QMA-complete? Has this been ...
3
votes
0answers
107 views

Describing state machines mathematically

The short paper "Computer Science and State Machines" by Leslie Lamport seems quite strange to me. On the one hand, I am surprised to see that an important hardware protocol called "two-phase ...
0
votes
1answer
114 views

Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$?

The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $. I wonder the following ...
-2
votes
0answers
28 views

How to describe the exponential nature of adding complexity [on hold]

Is there a computer science term that describes adding complexity to an IT system? For example, adding an application to an organization isn't N+1 it's exponential in the possible interactions it ...
1
vote
1answer
61 views

Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem: Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$. Output: a minimum weight ...
-2
votes
0answers
84 views

What is the minimum number of sign patterns in $\frac n2$ of columns (or rows) of Hadamard matrices? [on hold]

Given a Hadamard matrix of size $n$, I want to know what is the minimum number of unique sign patterns in any $\frac n2$ columns (or rows). I count a sign pattern and its negation to be the same. My ...
0
votes
2answers
40 views

A continuous center point of a convex spherical polygon

In discrete geometry, the center point $c$ of a discrete set $S$ of $n$ points in the plane is such that any half plane containing $c$ contains (roughly) $n/3$ points of $S$. (Such a center point ...
3
votes
2answers
103 views

Primitive Recursive Definition : Binary numbers

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the ...
3
votes
1answer
155 views

Random flows through fixed network

A flow network is a directed graph in which each edge has a capacity. A flow through this network is an assignment of a value to each edge that is less or equal to the edge capacity, and such that the ...
1
vote
0answers
33 views

inapproximability of logarithic factor of indepence set [on hold]

The hardness result derived using PCP theorem for Independent set suggests that there exists some absolute constant $\epsilon_0$ such that for $0< \epsilon < \epsilon_0$, it is hard to ...
0
votes
1answer
61 views

What is a minimum vertex separator as in this definition?

In a research paper the following definition appears that I'm not able to understand completely. Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
2
votes
1answer
74 views

Proof of an Ising model representation of graph isomorphism problem

I am going to through Ising formulations of many NP problems by Andrew Lucas. In section $9$ on page 22, the author introduced an exact Ising formulation of the graph isomorphism problem. Given two ...
4
votes
1answer
96 views

Type theory for memory safe data structures

Data structures such as a doubly linked list and a B+ tree have blocks of memory that have multiple pointers to it. This creates the risk that a bug will allow memory to be accessed after being freed. ...
2
votes
0answers
63 views

Padding Arguments for Probabilistic Classes

Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or ...
-5
votes
1answer
52 views

an algorithm for halting problem that is recursively enumerable [closed]

Halting problem is known to be undecidable and therefore no recursive algorithm for halting problem exists. However, I was wondering if recursively enumerable algorithm, that is Turing-recognizable ...
3
votes
2answers
68 views

What requirements should a denotational semantics for a programming language satisfy to be correct?

We have a programming language and its denotational semantic, like Tony Hoare's CSP with its syntax and denotational semantic e.g. stable failure and UTP. We want to extend the language (its ...
-1
votes
0answers
31 views

Finding the most part of common information

Let we have strings $x$ and $y$. I want to find the most part of extracting common information of $x$ and $y$, that is string $z$ with $C(z) + C(x|z) = C(x)$, $C(z) + C(y|z) = C(y)$, $C(z) \to max$ ...
0
votes
0answers
47 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
1
vote
0answers
108 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
9
votes
0answers
77 views

NEXPTIME-completeness with more time for reductions

One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
-1
votes
1answer
106 views

How can you prove that all halting probabilites are normal real numbers?

Wikipedia claims that any halting probability (Chaitin's constant) is a normal number. Since Chaitin's constant is uncomputble, how is a proof the the normalcy of the number possible? Computable ...
4
votes
0answers
147 views

Hardness of UNAMBIGUOUS-3DM

Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution. Is there a ...
2
votes
1answer
66 views

Resource listing models with known VC dimension

Is there any reference resource gathering models with known VC dimension? I am looking for an exhaustive list of models with their VC dimension (and ideally the associated proof or a pointer to it). ...
3
votes
1answer
140 views

Applications of Harrow's algorithm for solving linear equations

In Harrow's algorithm for solving a system of linear equations the output is a quantum state rather than explicit information. Has anyone been able to apply knowledge of this quantum state to solve a ...
0
votes
0answers
22 views

Video lectures on type systems [migrated]

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...
2
votes
0answers
33 views

Efficient Shamir secret sharing reconstruction

Shamir's secret sharing scheme is a well known way to convert a secret into a polynomial and distribute points in this polynomial. Some of these points can then be regrouped to reconstruct the ...
9
votes
0answers
112 views

How to find the “hard” probability distribution on the input for recursive boolean functions?

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
1
vote
0answers
90 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
5
votes
0answers
128 views

DAG reachability with O(n log n) space and O(log n)-time queries?

For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm ...

15 30 50 per page