# All Questions

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 ...
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)$ ...
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 ...
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 ...
18 views

### Solving Recurrences

This is the recursion available \ $$R_{n}=\frac{1}{n} \{C_1* R_{n-1} +C_2 * R_{n-2}\}, R_0 = A_0 ,R_1 = A_1$$ Given conditions $A_0,A_1,C_1,C_2$ are constant ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...