# Questions tagged [computer-science]

For question borderline with, or having application to, computer science. Consider also posting http://cs.stackexchange.com/ or http://cstheory.stackexchange.com/ instead of here, if appropriate.

479
questions

**74**

votes

**3**answers

3k views

### How feasible is it to prove Kazhdan's property (T) by a computer?

Recently, I have proved that Kazhdan's property (T) is theoretically provable
by computers (arXiv:1312.5431,
explained below), but I'm quite lame with computers and have
no idea what they actually ...

**72**

votes

**6**answers

10k 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 } (...

**69**

votes

**3**answers

5k views

### Wanted: a “Coq for the working mathematician”

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar with....

**63**

votes

**4**answers

9k 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 week,...

**62**

votes

**9**answers

16k 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 ...

**57**

votes

**30**answers

75k views

### What programming languages do mathematicians use? [closed]

I understand this might be a slightly subjective question, but I am honestly curious what programming languages are used by the mathematics community.
I would imagine that there is a group of ...

**50**

votes

**4**answers

3k views

### What algorithm in algebraic geometry should I work on implementing?

This summer my wife and one of my friends (who are both programmers and undergraduate math majors, but have not learned any algebraic geometry) want to learn some algebraic geometry from me, and I ...

**41**

votes

**7**answers

6k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference?
Long version of the question:
I'm sort of surprised to be asking this, because ...

**40**

votes

**1**answer

906 views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**39**

votes

**17**answers

11k views

### Computer Science for Mathematicians

This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet.
I've seen computer scientists post questions looking to learn things ...

**38**

votes

**3**answers

3k views

### “Simpler” statements equivalent to Con(PA) or Con(ZFC)?

Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...

**36**

votes

**8**answers

15k views

### Problems known to be in both NP and coNP, but not known to be in P

One such problem I know is integer factorization.
What are other interesting cases?

**35**

votes

**9**answers

4k views

### What is the shortest program for which halting is unknown?

In short, my question is:
What is the shortest computer program for which it is not known whether or not the program halts?
Of course, this depends on the description language; I also have the ...

**34**

votes

**12**answers

3k 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?
...

**34**

votes

**14**answers

3k 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.
...

**34**

votes

**0**answers

922 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 track ...

**30**

votes

**11**answers

2k views

### Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...

**30**

votes

**1**answer

3k views

### An edge partitioning problem on cubic graphs

Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...

**28**

votes

**16**answers

11k views

### Programming Languages Based on Category Theory

Since some computer scientists use category theory, I was wondering if there are any programming languages that use it extensively.

**27**

votes

**4**answers

2k 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 ...

**26**

votes

**10**answers

3k views

### Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not.
Are there some large $n$ ...

**24**

votes

**2**answers

3k views

### Counting subgraphs of bipartite graphs

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...

**23**

votes

**8**answers

3k views

### Between mu- and primitive recursion

It is well known that primitive recursion is not powerful enough
to express all functions, Ackermann function being probably the best
known example.
Now, in the logic courses (that I have had look at)...

**23**

votes

**3**answers

1k 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 ...

**23**

votes

**5**answers

1k views

### Securing privacy of “who communicates with whom” under Orwell-like conditions

Assume that there is a big and powerful country with an
information-greedy secret service which has backdoors to all internet nodes
throughout the world which permit him to observe all exchanged data ...

**23**

votes

**3**answers

1k views

### Expected edit distance

The edit or Levenshtein distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{...

**22**

votes

**4**answers

2k 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 ...

**21**

votes

**1**answer

4k 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 ...

**21**

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 ...

**21**

votes

**3**answers

660 views

### Defining computable functions categorically

Computable functions may be defined in terms of Turing machines or recursive functions, or some other model of computation. We normally say that the choice doesn't matter, because all models of ...

**21**

votes

**1**answer

639 views

### What, mathematically speaking, does it mean to say that the continuation monad can simulate all monads?

In various places it is stated that the continuation monad can simulate all monads in some sense (see for example http://lambda1.jimpryor.net/manipulating_trees_with_monads/))
In particular, in http://...

**20**

votes

**4**answers

1k views

### Kolmogorov complexity is the strongest noncomputable function

Yury I. Manin says that Kolmogorov complexity (in some nontrivial sense) is the strongest noncomputable function ("Колмогоровская сложность... невычислима... она во многих интересных смыслах ...

**20**

votes

**3**answers

4k views

### Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...

**19**

votes

**3**answers

894 views

### Which distributions can you sample if you can sample a Gaussian?

Explicitly: You have a computer that is able to pick a real number at random according to the normal distribution: $\mathcal{N}(0,1) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Which distributions can this ...

**19**

votes

**3**answers

927 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 a ...

**18**

votes

**2**answers

1k views

### Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...

**18**

votes

**3**answers

2k views

### What is the history of the Y-combinator?

Inspired by the comments to this question, I wonder if someone can explain the history of the fixed point combinator (often called the Y combinator) in lambda calculus.
Where did it first appear? ...

**18**

votes

**3**answers

1k views

### How do we express measurable spaces using type theory?

A measurable space $(X,\mathcal X)$ consists of a set $X$ equipped with a $\sigma$-algebra of subsets $\mathcal X$. I would like to write computer programs involving measurable spaces, but to the best ...

**18**

votes

**3**answers

897 views

### Can you consistently add axioms about the Busy Beaver function to ZF?

Consider a Turing Machine with $N$ states which checks all theorems of ZF and halts upon finding a contradiction. If ZF were consistent and could prove the value of $BusyBeaver(N)$, then it would be ...

**18**

votes

**1**answer

2k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**18**

votes

**0**answers

690 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 ...

**17**

votes

**5**answers

759 views

### Mathematics of privacy?

I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics?
Can we ...

**17**

votes

**1**answer

1k views

### Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...

**17**

votes

**1**answer

1k views

### Is there an unambiguous CFL whose complement is not context-free?

I'm doing a little bit of research about context-free languages. A question that's popped up is whether or not there exists an unambiguous context-free language whose complement is not a context-free ...

**16**

votes

**6**answers

2k views

### SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...

**16**

votes

**3**answers

1k 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 ...

**16**

votes

**1**answer

7k views

### Meaning of $\Subset$ notation

The symbol $\Subset$ (occurring in places where $\subseteq$ could occur syntactically) comes up frequently in a paper I'm reading. The paper lives at the intersection of a few areas of math, and I ...

**16**

votes

**2**answers

664 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 ...

**15**

votes

**9**answers

867 views

### Combinatorial constructions found by computer

In preparation for a talk I am giving to our undergraduate mathematics society, I am trying to collect examples of combinatorial constructions that were found by computer. Thus my question is the ...

**15**

votes

**7**answers

1k views

### Two questions from combinatorics on words

Question 1. Assume that an infinite word $u\in\{0,1\}^{\mathbb Z}$ is not balanced. Is it true that there exists a finite 0-1 word $w$ such that $0w01w1$ or $1w10w0$ is a factor of $u$? Is it true ...