<ol>
<li><p>What is the computational complexity of computing <a href="https://en.wikipedia.org/wiki/Ramsey%27s_theorem" rel="nofollow">Ramsey numbers</a> $(n,m) \mapsto R(n,m)$? Is it inside PH?</p></li>
<li><p>Would it be easier to compute $R$ if PH=P?</p></li>
</ol>

CC BY-SA 3.0
2016-01-25T20:07:59.147Z
Thanks. I had not seen the Q. As you pointed out it seems to be still open. I was assuming it lies in the PH, but am/was not sure where and how to prove it. Thus, Q2. (i.e. Assuming P=NP, then what can we say about the complexity for finding them in that scenario). But, I think the question of finding them assuming the collapse seems to be open. The worst case complexity for a particular Graph size is  O(c^(n(2))), but we have no idea how fast the graph grows with the Ramsey parameters, as asymptotic bound gap grows exponentially.
TheoryQuest1
CC BY-SA 3.0
2016-01-26T11:49:25.910Z
The question does not make sense to me. Polynomial hierarchy consists of decision problems, whereas you are asking about a function problem, so you are comparing apples and oranges. Moreover, the Ramsey numbers are exponentially large, hence you need exponential time just to write them down, let alone to compute them, and having oracles from PH cannot help that.
Emil Jeřábek
CC BY-SA 3.0
2016-01-26T12:09:21.277Z
I am naive regarding Ramsey Numbers with that disclaimer: The asymptotic bounds are exponential in nature, but I am confused as this quote from you on the other problem: 'We don’t really know much about the Ramsey numbers. It’s perfectly possible they are given by a nice formula, computable in polynomial time.' Thus, assuming we may have such a formula, we might somehow (no idea how) be able to reduce the verification of those numbers to a polynomial time problem. Hence, as far as I understand, their calculation (and even verification) might be strictly Polynomial.
TheoryQuest1
CC BY-SA 3.0
2016-01-26T15:15:26.880Z
You are quoting me out of context, which concerned problems whose inputs were actual graphs, hence the size was effectively given in unary. I even explicitly pointed that out in the same comment thread. No matter what formulas might exist, (1) calculation of Ramsey numbers is a function problem, hence it is a priori meaningless to ask about its containment in a class of decision problems, and (2) the output size is exponential in the input size, hence it cannot be computed in subexponential time. If you don't understand such basic facts, you can't understand the question you're asking.
Emil Jeřábek
CC BY-SA 3.0
2016-01-26T15:18:20.127Z
FWIW, Ramsey numbers are computable in $\mathrm{FEXP^{NP}}$ using straightforward binary search.
Emil Jeřábek
CC BY-SA 3.0
2016-01-26T22:09:54.117Z
@PhilipWhite: No, no, no, no. A polynomial-time oracle Turing machine cannot write more than polynomially many bits of output. It makes no difference whatsoever if the oracle is from P, from PH, or highly undecidable.
Emil Jeřábek
CC BY-SA 3.0
2016-01-27T10:33:00.563Z
@PhilipWhite: No. It makes sense to ask if a function problem *reduces* to a class of decision problems by a particular kind of reductions. It doesn't make sense to ask if the function problem *is* in such a class. If the OP asked whether a function problem is in P, the answer would be an unequivocal no. P is not FP, and PH is not FPH.
Emil Jeřábek
CC BY-SA 3.0
2016-01-27T12:39:59.357Z
Much thanks for the informative comments. As I said, I did not have much background in Ramsey Theory. The trigger was a rather humorous note regarding the PH Collapse (http://www.scottaaronson.com/writings/phcollapse.pdf) . And was wondering what other concrete problems (not just Complexity Classes), that wold survive the complete PH Collapse, would be open, and would be worthwhile attempting to get a concrete solution - Algorithm, Formula (functional, decision etc). In this regard I stumbled upon Ramsey Numbers. Hence, the Q.
TheoryQuest1
<cc.complexity-theory><co.combinatorics>
Computational Complexity of Ramsey Numbers
TheoryQuest1
# Computational Complexity of Ramsey Numbers

(Asked by: username_0 on 2016-01-25)

1. What is the computational complexity of computing [Ramsey numbers](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) $(n,m) \mapsto R(n,m)$? Is it inside PH?
2. Would it be easier to compute $R$ if PH=P?

**Tags:** cc.complexity-theory, co.combinatorics

> **Comments:**
> **username_0**: Thanks. I had not seen the Q. As you pointed out it seems to be still open. I was assuming it lies in the PH, but am/was not sure where and how to prove it. Thus, Q2. (i.e. Assuming P=NP, then what can we say about the complexity for finding them in that scenario). But, I think the question of finding them assuming the collapse seems to be open. The worst case complexity for a particular Graph size is  O(c^(n(2))), but we have no idea how fast the graph grows with the Ramsey parameters, as asymptotic bound gap grows exponentially.  
> **username_1**: The question does not make sense to me. Polynomial hierarchy consists of decision problems, whereas you are asking about a function problem, so you are comparing apples and oranges. Moreover, the Ramsey numbers are exponentially large, hence you need exponential time just to write them down, let alone to compute them, and having oracles from PH cannot help that.  
> **username_0**: I am naive regarding Ramsey Numbers with that disclaimer: The asymptotic bounds are exponential in nature, but I am confused as this quote from you on the other problem: 'We don’t really know much about the Ramsey numbers. It’s perfectly possible they are given by a nice formula, computable in polynomial time.' Thus, assuming we may have such a formula, we might somehow (no idea how) be able to reduce the verification of those numbers to a polynomial time problem. Hence, as far as I understand, their calculation (and even verification) might be strictly Polynomial.  
> **username_1**: You are quoting me out of context, which concerned problems whose inputs were actual graphs, hence the size was effectively given in unary. I even explicitly pointed that out in the same comment thread. No matter what formulas might exist, (1) calculation of Ramsey numbers is a function problem, hence it is a priori meaningless to ask about its containment in a class of decision problems, and (2) the output size is exponential in the input size, hence it cannot be computed in subexponential time. If you don't understand such basic facts, you can't understand the question you're asking.  
> **username_1**: FWIW, Ramsey numbers are computable in $\mathrm{FEXP^{NP}}$ using straightforward binary search.  
> **username_1**: @PhilipWhite: No, no, no, no. A polynomial-time oracle Turing machine cannot write more than polynomially many bits of output. It makes no difference whatsoever if the oracle is from P, from PH, or highly undecidable.  
> **username_1**: @PhilipWhite: No. It makes sense to ask if a function problem *reduces* to a class of decision problems by a particular kind of reductions. It doesn't make sense to ask if the function problem *is* in such a class. If the OP asked whether a function problem is in P, the answer would be an unequivocal no. P is not FP, and PH is not FPH.  
> **username_0**: Much thanks for the informative comments. As I said, I did not have much background in Ramsey Theory. The trigger was a rather humorous note regarding the PH Collapse (http://www.scottaaronson.com/writings/phcollapse.pdf) . And was wondering what other concrete problems (not just Complexity Classes), that wold survive the complete PH Collapse, would be open, and would be worthwhile attempting to get a concrete solution - Algorithm, Formula (functional, decision etc). In this regard I stumbled upon Ramsey Numbers. Hence, the Q.  

---

## 0 answers

