**3**

votes

**1**answer

186 views

### Is there an easy decision algorithm for the inhabitation problem for simple types?

Consider the basic system of simple types usually known as $TA_\lambda$. One can prove that (as a consequence of the Subject Reduction Property and the fact that any typable term is strongly ...

**-4**

votes

**0**answers

30 views

### Hamiltonian systems plus epsilon [on hold]

EDIT: A $2n$-dimensional hamiltonian system is completely integrable if it has $n$ linearly independent (over $\mathbb R$) conserved observables ($C^\infty$ functions on phase space, among which is ...

**-2**

votes

**0**answers

34 views

### how to solve recurrence using substitution method T (n) = T (n-1) + c [on hold]

how to solve recurrence using substitution method T (n) = T (n-1) + c
how to solve this recurrence T (n) = T (n-1) + c using substitution method for Advanced Algorithm Analysis and Design purpose

**14**

votes

**2**answers

375 views

### Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...

**33**

votes

**2**answers

2k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this ...

**10**

votes

**2**answers

2k views

### Best-case Running-time to solve an NP-Complete problem

What is the fastest algorithm that exists to solve a particular NP-Complete problem? For example, a naive implementation of travelling salesman is $O(n!)$, but with dynamic programming it can be done ...

**0**

votes

**2**answers

458 views

### What is a maximal set in the context of argumentation in AI [closed]

I am computer scientist, not a mathematician, I've been reading some papers on argumentation in AI that uses the term 'maximal' set without defining it. I think it's left undefined because it's a ...

**1**

vote

**0**answers

31 views

### Efficient SVD of a matrix without some of the columns

I have a matrix $A \in \mathbb{R}^{p \times q}$ of rank $r$ and its SVD decomposition, i.e,
$$
A = U S V^\top,
$$
where $U \in \mathbb{R}^{p \times r}$ and $V \in \mathbb{R}^{q \times r}$ are ...

**4**

votes

**1**answer

69 views

### What class of probability distributions do probabilistic turing machines induce? [closed]

What class of probability distributions is induced by the class of probabilistic turing machines? Is there a precise characterization?

**1**

vote

**0**answers

53 views

### Monoidal cats and string diagrams for a semantics of object oriented programming languages

It seems to me that in a statically typed, object oriented language, there is a striking similarity to wiring diagrams. Wires (objects) of type $X$ go into functions (boxes) of input type $X$. Is ...

**13**

votes

**0**answers

124 views

### Complexity classes for BSS machines

Given a first-order structure $\mathcal{S}$, a Blum-Shub-Smale machine on $\mathcal{S}$ is essentially a Turing machine where
Cells on the tape can hold arbitrary elements of $\mathcal{S}$.
The ...

**8**

votes

**0**answers

64 views

### numerical methods to compute approximated Stiefel-Whitney class

Let $0<\epsilon<1$, $k\geq 4$ be an integer, $S^2$ be the unit sphere in $\mathbb{R}^3$, $d$ the Euclidean distance in $\mathbb{R}^3$ and
$$
...

**4**

votes

**1**answer

411 views

### The relationship between P vs NP problem and “Kolmogorov complexity with time”

Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.
Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"
Is it Problem1 $\in ...

**7**

votes

**1**answer

129 views

### Shortest vector problem over polynomials

In shortest vector problem, given a lattice in $\Bbb Z^n$, we seek the shortest non-zero vector in the lattice. This problem is computationally difficult.
Is there a polynomial analog of this problem ...

**0**

votes

**0**answers

386 views

### Extended definition of unambiguous language and the existence of unambiguous grammar

Let's extend the unambiguity of language and grammar as follows:
a language $L$ is unambiguous if there is a grammar that generates every word in $L$ in a unique way, the grammar may be of type 0 or ...

**1**

vote

**0**answers

35 views

### Canonical representation of binary decision trees in Ptime?

I am wondering about the possibility of efficiently (here: in Ptime) representing binary decision trees (BDT) by some other data structure in a way that characterizes their equivalence.
More ...

**3**

votes

**1**answer

109 views

### Equivalence between Diffie Hellman and Discrete Log

For which non-trivial groups, do we know that the Diffie Hellman problem and the Discrete Log are equivalent?
Is there any group for which we suspect them to be different?
Could there be a finite ...

**51**

votes

**4**answers

5k views

### Can we cover the unit square by these rectangles?

The following question was a research exercise (i.e. an open problem) in R. Graham, D.E. Knuth, and O. Patashnik, "Concrete Mathematics", 1988, chapter 1.
It is easy to show that
$$\sum_{1 \leq k } ...

**1**

vote

**0**answers

22 views

### Open volumetric time series data set

Does anyone know where I can find a good open volumetric time series data set?
I had a look at some of Stanford's open data sets (https://graphics.stanford.edu/data/voldata/ )
But these do not seem ...

**7**

votes

**1**answer

164 views

### “Separated” version of Sauer's lemma on VC classes

Sauer's lemma, a well-known result in computational complexity theory, learning theory, and combinatorics, states the following:
Let $\Phi$ be a collection of subsets of a set $U$, and assume that ...

**16**

votes

**3**answers

699 views

### Status of an open problem about semilinear sets

In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is ...

**1**

vote

**0**answers

60 views

### Optimal reduction using token-passing nets

I am looking for implementation of optimal reduction for λ-calculus based on interaction nets (McCarthy's amb allowed) in the spirit of "Token-Passing Nets: Call-by-Need for Free" by François-Régis ...

**5**

votes

**0**answers

104 views

### Constructive Mathematics and Termination [closed]

In the book "The Universal Turing Machine A Half-Century Survey" there is a paper called "The Confluence of Ideas in 1936" by Robin Gandy. In section 4.2, Gandy writes:
"If one accepts, on whatever ...

**1**

vote

**1**answer

49 views

### floating point representation via the perspective of TTE/computable analysis

Floating point numbers are not compatible with the usual theory of type 2 theory of effectivity (TTE), and not even the real-RAM model; there are functions that are computable in one model but not ...

**29**

votes

**13**answers

2k views

### Where have you used computer programming in your career as an (applied/pure) mathematician?

For background: I'm working on a book to help mathematicians learn how to program. However, I need to see some examples from people in the field that have done different kinds of things than I have.
...

**9**

votes

**6**answers

2k views

### Aren't “oracle machines” unsound concepts? [closed]

From Wikipedia (bold emphasis at the end is mine):
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as ...

**18**

votes

**0**answers

530 views

### Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...

**-1**

votes

**1**answer

230 views

### Are limits decidable? Should definitions be decidable? [closed]

This question is about the Turing computability of the $\epsilon-N$ definition of a limit of an infinite sequence $S$. First, a proposition:
There cannot exist a Turing Machine $M$ which, given a ...

**3**

votes

**0**answers

104 views

### Oracle queries asked in parallel

Definition: Assume that $\phi(q)$ is of the form $\exists y \leq 2^{p(n)} \varphi(q,y)$, where $p$ is a polynomial and $n = |q|$ (i.e. $n$ is the length of the binary representation of $q$). Then a ...

**3**

votes

**0**answers

228 views

### Possible $\mathsf{NP}$ complete problem from number theory

A candidate $\mathsf{NP}$ complete variant of factoring was posted in http://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring, where decision problem ...

**5**

votes

**2**answers

179 views

### If $f : [-a,a] \rightarrow \mathbb{IR}$ is Scott continuous, why are $f^-$ and $f^+$ measurable?

In "A domain theoretic account of Picard's theorem" (http://www.doc.ic.ac.uk/~dirk/Publications/icalp2004.pdf), the authors assert the following.
Let $\mathbb{IR}$ be the interval domain $\lbrace ...

**6**

votes

**0**answers

218 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**1**

vote

**1**answer

50 views

### Finding t vlaue in Bezier curve [closed]

According to this question, I'm looking for some method to find the t value in Quadratic bezier curve equation:
$$
B(t)=P_0+t(1-t)P_1+t^2P_2 \space \space where \space 0 ≤ t ≤ 1
$$
In this ...

**6**

votes

**1**answer

143 views

### Algorithm that generates a n-simplex that cover n-polytope?

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?

**22**

votes

**3**answers

842 views

### What technical and/or theoretical challenges are involved in automatically extracting proofs from books and papers into Coq code?

Over the years, advances in machine learning has allowed us to communicate and interact, using the same natural language, more and more semantically with computers, e.g. Google, Siri, Watson, etc. On ...

**0**

votes

**0**answers

46 views

### Finding a movement taking out of a convex set

There is a convex set $S$ as the hull of M points in an D-dimensional Euclidean space and a point $\vec P$ in the set. Then, there is a set of vectors $\vec W$ taking the form $\vec W=\sum_{i=1}^N ...

**7**

votes

**0**answers

150 views

### Distribution of trivial subset sums

Suppose I have a set $S$ of $n$ integers picked independently, uniformly at random from $[-L, L].$ Let $z(S)$ be the number of subsets of $S$ which sum to zero. The question is: what is the ...

**11**

votes

**3**answers

696 views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**19**

votes

**4**answers

2k views

### does the “convolution theorem” apply to weaker algebraic structures?

The Convolution Theorem is often exploited to compute the convolution of two sequences efficiently: take the (discrete) Fourier transform of each sequence, multiply them, and then perform the inverse ...

**2**

votes

**1**answer

281 views

### Functional programing and intensional type theory

I know very little about how computers work, so please excuse my ignorance!
I think of the Glasgow Haskell Compiler as a program that eats up extensional type theory and spits out a program which ...

**3**

votes

**0**answers

141 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**-4**

votes

**1**answer

139 views

### What exactly is wrong with this statement (Lucas-Penrose fallacy)? [closed]

Statement
"For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method."
...

**5**

votes

**1**answer

377 views

### Constructing the oracle for Grover's algorithm

For a final project in my class, I decided to try to simulate a quantum computer and implement Grover's algorithm. I followed this excellently written blog post by Craig Gidney, and was successful in ...

**0**

votes

**1**answer

1k views

### How are taps proven to work for LFSRs?

Obviously, you can exhaustively check that it lands on every state except the zero state, but for large linear feedback shift registers (LFSR), this quickly becomes infeasible.
Wikipedia states the ...

**11**

votes

**1**answer

542 views

### Can Shor's Algorithm be modified to run efficiently on a classical computer?

Shor's algorithm is an algorithm which factors integers in polynomial time on a quantum computer. If one tries to run it on a classical computer, one runs into the problem that the state vector that ...

**52**

votes

**9**answers

12k views

### Relating Category Theory to Programming Language Theory

I'm wondering what the relation of category theory to programming language theory is.
I've been reading some books on category theory and topos theory, but if someone happens to know what the ...

**4**

votes

**1**answer

216 views

### Constructing hard inputs for the complement of bounded halting

If there is always a hard input for the complement of bounded halting, can that input be constructed?
More precisely, suppose that
for any deterministic TM $M$ accepting
$$
...

**1**

vote

**1**answer

165 views

### Total conditional complexity

By $C(|)$ denote conditional complexity.
By $CT(|)$ denote total conditional complexity.
For every n there exist two strings $x$ and $y$ of length $n$ such that $C(x|y) = O(1)$
but $CT(x|y) \ge n $.
...

**2**

votes

**0**answers

97 views

### Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$.
For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...

**5**

votes

**2**answers

865 views

### How to calculate the sum of remainders of N?

I'm trying to sum the remainders when dividing N by numbers from 1 up to N
$$\sum_{i = 1}^{N} N \bmod i$$
It's easy to write a program to evaluate the sum if N is small in O(N) but what if N is large ...