**3**

votes

**1**answer

181 views

### Various notions of Turing reduction for partial functions

If $f$ and $g$ are partial functions $\mathbb{N} \to \mathbb{N}$, define six preorder relations $f \preceq g$ as follows:
$f \mathop{\preceq_{\mathrm{S}}} g$ ("$f$ is strict/Sasso reducible to $g$") ...

**2**

votes

**0**answers

156 views

### A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem).
Q1- But I am not sure whether ...

**1**

vote

**0**answers

309 views

### The used symbols for equality and equivalence

Background: I am currently developing a general purpose programming language which allows formal verification (i.e. correctness proofs) of programs. During the development it came out that a lot of ...

**4**

votes

**2**answers

277 views

### Definition of continuous functions in order theory

If we have a complete partial order (i.e. directed complete) I find frequently the following definition of a continuous function. A function $f:A\to B$ where $A$ and $B$ are cpos is called continuous ...

**9**

votes

**0**answers

268 views

### Various definitions of recursion from ordinal machines

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...

**0**

votes

**1**answer

195 views

### hypergraph cartesian join operation (over same vertex set)

consider two hypergraphs $H_1 = (V, \mathscr{E}_1), H_2 = (V, \mathscr{E}_2)$ over the same vertex set $V$. am interested in what could be called a "cartesian join" operation building a new hypergraph ...

**3**

votes

**2**answers

250 views

### What categories correspond to the typed lambda calculus with parametric types?

the unadorned typed lambda calculus correspond to the closed cartesian categories, but if we add in dependent or parametric types how are they then characterised?

**3**

votes

**0**answers

316 views

### Groupoid interpretation of type theory

Hello,
I read the paper on groupoid interpretation of type theory by Hofmann and Streicher and I have a question. According to the authors $Tm([[\text{Set}\:[\Gamma]\: ]])$ is the same as ...

**0**

votes

**1**answer

252 views

### Counterexamples for this algorithm for recognizing lexicographic product of graphs?

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT
(since 2SAT is polynomial, the algorithm is polynomial).
Can't prove completeness of the algorithm and since it is ...

**0**

votes

**0**answers

85 views

### Exact Length Problem in a directed graph

I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the ...

**4**

votes

**1**answer

542 views

### Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...

**5**

votes

**1**answer

645 views

### How much does a quantum oracle to find a needle in a haystack really cost?

Among the basic algorithms of quantum computations Lov Grover's result on quantum search stands out, both in regards to its intrinsic interest, and for its undisputable elegance.
Grover's algorithm ...

**9**

votes

**3**answers

1k views

### Higher categories as data structures

Still wading through higher category theory. I find the subject a bit intimidating, not so much for technical reasons, but because I lack sufficient intuition as to the motivation(s)/heuristics one ...

**6**

votes

**1**answer

426 views

### Who introduced the concept of Primitive recursive functions?

I have thought that Gödel introduced the concept of Primitive recursive functions in his seminal paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme" (I hope I ...

**6**

votes

**0**answers

148 views

### Finding a database of representations as matrices

Sorry if this would be more appropriate as a stackoverflow and not a mathoverflow question, but I think it's more likely to be known in this community.
There are plenty of places on the internet or ...

**1**

vote

**2**answers

268 views

### Satisfiability problem for FOL[<,R]

Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...

**4**

votes

**3**answers

289 views

### Existential quantification over regular predicates

A regular language over an alphabet $\Sigma$ is a subset of the set of all words over $\Sigma$ that can be accepted by some finite automaton. A regular language identifies a certain property of ...

**7**

votes

**0**answers

234 views

### Modelling the difficulty of mental calculation. [closed]

Are you aware of any work that tries to model the difficulty of evaluating a formula mentally (for your average, numerate, person, not a trained mental calculator)?
For instance, evaluating an ...

**0**

votes

**1**answer

284 views

### Is there any relationship between a tree(graph theory) and semi-metric?

suppose we have a tree(undirected) with $n$ vertices.The edges are weighted(distances). Is it possible to impose a semi-metric structure on the graph using these distances and adjacency matrix?

**20**

votes

**4**answers

1k views

### Algorithmically unsolvable problems in topology

This question is inspired by a paper by B. Poonen that appeared on the arxiv some time ago: http://arxiv.org/abs/1204.0299. The paper gives a sample of algorithmically unsolvable problems from various ...

**3**

votes

**2**answers

340 views

### anyone help me with this inequality

I'm have some difficulties in bounding the following inequality:
I want to find a c as small as possible s.t.
$$\sum_{i=1}^nx_i^4\sum_{i=1}^nx_i^2 -\sum_{i=1}^nx_i^6 \leq ...

**3**

votes

**2**answers

963 views

### Is there an algorithm that can “reverse engineer” a Regular Expression?

Given a Regular language (represented as a black box to which one can apply inputs and get 0/1) Is there an algorithm that can find a finite deterministic automaton that produces that language?

**5**

votes

**0**answers

198 views

### Büchi automata with acceptance strategy

I have already asked this question on cstheory.stackexchange, but without success. Maybe it is too close to an "open problem", although it is not a famous one. Anyway I try here, I can always remove ...

**2**

votes

**1**answer

334 views

### Algorithm for satisfiability of inequalities.

I am looking for an algorithm for checking the satisfiability (with natural values) of a set of inequalities made of variables and natural numbers, for example: $u < v, u \leq z, 3 \leq v$.
In ...

**0**

votes

**0**answers

349 views

### Examples of Hamiltonian Cycle Problem / Traveling Salesman Problem in general grid graph form

I understand that there is a polynomial algorithm to solve TSPs that are in solid grid graph form (grid graphs without holes).
I am particularly interested in the non-solid grid graph form of the ...

**3**

votes

**1**answer

192 views

### Bezier Curves question

Hi everyone
I have a fairly simple question about bezier curves: can you represent n bezier curves that have been continuously joined together by a single bezier curve of degree 3n?
My instinct is ...

**2**

votes

**1**answer

463 views

### #P version of SUBSET SUM

The decision version of the SUBSET SUM problem asks the following: Given a set of integers $S =$ {$a_1, ..., a_n$}, is there a subset $S'$ of $S$ such that the sum of the elements in $S'$ is equal to ...

**0**

votes

**1**answer

245 views

### Universality of blind graph rewriting

Let us consider $S(M) = \{(f_0, f_1) | f_0, f_1: M \rightarrow M\}$, where $M$ is a finite set. Each element of $S(M)$ is equivalent to a finite directed
graph with the set of nodes $M$, which has ...

**3**

votes

**2**answers

333 views

### Representation of μ-recursive functions

Can every μ-recursive function be defined using a single instance of the μ operator applied to a primitive recursive function?
According to Wikipedia, any μ-recursive function can be expressed as the ...

**3**

votes

**1**answer

639 views

### Algebraic structure generated by primitive graph operations

Let $M$ be a finite set, and
$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.
Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...

**23**

votes

**11**answers

2k views

### Interesting conjectures “discovered” by computers and proved by humans?

There are notable examples of computers "proving" results discovered by mathematicians, what about the opposite:
Are there interesting conjectures "discovered" by computers and proved by humans?
...

**3**

votes

**2**answers

614 views

### symmetric difference of languages - both are in NP and coNP

I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2$ = {x | x is in exactly one of ...

**25**

votes

**0**answers

647 views

### Computer calculations in A_infinity categories?

Is there a good computer program for doing calculations in A-infinity categories?
Explicit calculations in A-infinity categories are an important, useful, yet very tedious task. One has to keep ...

**6**

votes

**2**answers

876 views

### Busy Beaver - Proof for BB(2) = 4

Hi,
I need to prove the above claim.
I can show that $BB(2)\ge 4$ by building a turing machine,
but how can i show that $BB(2) \le 4$?
Searched a lot over the web, and saw that Rado proved it in ...

**3**

votes

**2**answers

732 views

### Certain type of regular languages

Dear All,
there is one type of regular languages, over $\{a,b\}$, which appear naturally in what I am studying, so if anybody could recognise them, or say any sort of their characterisation, that ...

**3**

votes

**2**answers

610 views

### Kleene's fixed point theorem on recursive subsets of computable functions

I have a question about the possibility to apply/restate the Kleene fixed point theorem on recursive subsets of computable functions. I don't know if this is trivial and/or if related questions have ...

**5**

votes

**1**answer

388 views

### Arrangement of integers 1..k^2 in k*k grid to minimize energy function

Question arises from considering cache oblivious algorithms.
What is the optimal way arrange the numbers $1$ to $k^2$ in a grid, to minimize to average difference between any two neighbouring ...

**7**

votes

**3**answers

603 views

### Error correcting codes - basic question

Hi,
I have a basic question regarding error correcting codes. Suppose I want to encode a finite information $F$ (say a finite string) into a string $x$ of $n$ bits ($n$ can be as large as you want), ...

**21**

votes

**4**answers

987 views

### A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others?
I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...

**2**

votes

**2**answers

539 views

### Graph Theory Conjectures [closed]

What are some important conjectures in graph theory that have been checked by computer up to order 11?

**6**

votes

**1**answer

321 views

### compression of a Turing machine run sequence

consider a Turing machine with a set of states $s_n$ and alphabet symbols $a_n$. now consider a "run sequence" generated from a starting input in the following sense. the run sequence is defined as ...

**2**

votes

**0**answers

106 views

### How to argue about state transitions?

Computing differs from math by its dependence on state changes, among other things. A program can be seen as a composition of state transitions, and it would be nice to have an inverse function to ...

**2**

votes

**1**answer

471 views

### Composite finite-state machines

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it ...

**1**

vote

**2**answers

441 views

### Is there constructive proof of the fact that every recursive set $A \ne \varnothing$ is recursively enumerable in non-decreasing order?

Every proof I've read about this fact considers two cases: $A$ - finite and $A$ - infinite but this is undecidable problem. So, is there constructive proof?

**8**

votes

**2**answers

310 views

### Reduction rules for inductive types

(I'm not sure if I should post this here rather than at Theoretical Computer Science, I've found a lot of type theory related questions on MathOverflow)
I'm working in Martin-Löf type theory with ...

**0**

votes

**1**answer

151 views

### Subset-Free Codes

For each non-negative integer $n$, what antichain(s) in $\{0,1\}^n$ with the pointwise partial order: $\;\;$ 1. $\;$ have the most elements $\;\;$ 2. $\;$ minimize the maximum of its elements' sum ...

**6**

votes

**2**answers

1k views

### Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication.
First, this is not exactly how monoids work, and second, this ...

**4**

votes

**2**answers

204 views

### What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title.
Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary ...

**7**

votes

**2**answers

863 views

### Distribution of the computable numbers on the real number line

If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...

**12**

votes

**1**answer

2k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...