<p>Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this value is $\vartheta(G)$). Assuming the Shannon capacity problem is non-computable, can one expect to have a different computable function that can lower the lower limit on $r$ (assume that function takes values of $\vartheta(G)$ wherever it is tight)?</p>

CC BY-SA 3.0
2013-12-09T13:12:59.207Z
We have a proof that the Lovasz theta function is not tight for some graph $G$. Consider a function which equals the Lovasz theta function for all graphs except $G$, but differs from the Lovasz theta function $G$.
Peter Shor 
CC BY-SA 3.0
2013-12-09T13:55:14.950Z
$\vartheta(G)$ is not tight for all $G$ is accommodated in the question. If one considers $\vartheta(G)$ as a coNP certificate, is there a certificate that is short and computable and give tighter than $\vartheta(G)$ for graphs for which $\vartheta(G)$ is not tight? This is the question I intended to ask in here. The computable function should take $\vartheta(H)$ values for graphs $H$ that are known to be tight for $\vartheta(H)$(like pentagon) and for other graphs produce proven tighter result?
Turbo
CC BY-SA 3.0
2013-12-09T13:59:26.097Z
So you want a certificate that does better than ϑ(G) for ***all*** graphs where ϑ(G) is not tight? That would give an algorithm that decides whether ϑ(G) is tight for a given graph, which I am pretty sure is a problem not known to be in P.
Peter Shor 
CC BY-SA 3.0
2013-12-09T14:03:28.803Z
Sure but is such a function computable for all graphs?
Turbo
CC BY-SA 3.0
2013-12-09T14:05:07.093Z
I don't understand your question now. If there is a different method than the Lovasz theta function of getting a bound on the Shannon capacity, then just take the minimum of the theta function and the other method. If the other method is computable, the minimum is a computable function.
Peter Shor 
CC BY-SA 3.0
2013-12-09T14:07:37.323Z
Well I am asking exactly in this direction. Does there exist such a function. Noga Alon shows that The capacity problem may be undecidable. However is the problem of tightness of $\vartheta(G)$ decidable for all graphs. This is I think the line of the question.
Turbo
CC BY-SA 3.0
2013-12-09T18:01:50.070Z
dont understand this sentence starting "Assuming the Shannon capacity problem is computable/non-computable..." how can you assume it is both/opposites? dont you mean you are assuming it is computable? also can you give a ref for alon proving it may be undecidable?
vzn
CC BY-SA 3.0
2013-12-09T18:40:48.087Z
changed to non-computable (having computable there does not make sense).
Turbo
<computability><it.information-theory>
Lovasz Theta as a short certificate
Turbo
# Lovasz Theta as a short certificate

(Asked by: username_0 on 2013-12-09)

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this value is $\vartheta(G)$). Assuming the Shannon capacity problem is non-computable, can one expect to have a different computable function that can lower the lower limit on $r$ (assume that function takes values of $\vartheta(G)$ wherever it is tight)?

**Tags:** computability, it.information-theory

> **Comments:**
> **username_1**: We have a proof that the Lovasz theta function is not tight for some graph $G$. Consider a function which equals the Lovasz theta function for all graphs except $G$, but differs from the Lovasz theta function $G$.  
> **username_0**: $\vartheta(G)$ is not tight for all $G$ is accommodated in the question. If one considers $\vartheta(G)$ as a coNP certificate, is there a certificate that is short and computable and give tighter than $\vartheta(G)$ for graphs for which $\vartheta(G)$ is not tight? This is the question I intended to ask in here. The computable function should take $\vartheta(H)$ values for graphs $H$ that are known to be tight for $\vartheta(H)$(like pentagon) and for other graphs produce proven tighter result?  
> **username_1**: So you want a certificate that does better than ϑ(G) for ***all*** graphs where ϑ(G) is not tight? That would give an algorithm that decides whether ϑ(G) is tight for a given graph, which I am pretty sure is a problem not known to be in P.  
> **username_0**: Sure but is such a function computable for all graphs?  
> **username_1**: I don't understand your question now. If there is a different method than the Lovasz theta function of getting a bound on the Shannon capacity, then just take the minimum of the theta function and the other method. If the other method is computable, the minimum is a computable function.  
> **username_0**: Well I am asking exactly in this direction. Does there exist such a function. Noga Alon shows that The capacity problem may be undecidable. However is the problem of tightness of $\vartheta(G)$ decidable for all graphs. This is I think the line of the question.  
> **username_2**: dont understand this sentence starting "Assuming the Shannon capacity problem is computable/non-computable..." how can you assume it is both/opposites? dont you mean you are assuming it is computable? also can you give a ref for alon proving it may be undecidable?  
> **username_0**: changed to non-computable (having computable there does not make sense).  

---

## 0 answers

