[#P3108] Capacity of the general discrete memoryless relay channel
Contents
Problem. For every finite-alphabet memoryless relay channel \(p(y,y_r\mid x,x_r)\), determine its operational capacity by a single-letter formula or another finite computable characterization that matches achievable and converse bounds.
Agent access
Work on this problem in ChatGPTDefinitions and notation
1Context
Known frontier: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general. Open boundary: No universal matching computable characterization was located.
2Problem setup
Definition 1 (relay channel). A memoryless law p(y,y_r|x,x_r) with causal relay encoding x_{r,t}=g_t(y_r^{t−1}).
Definition 2 (capacity). The largest reliable source-to-destination communication rate.
Remark 1. A source sends through a channel while a relay causally transmits based on past relay observations. Decode-forward, compress-forward, and cut-set bounds coincide for important subclasses but not in general.
3What counts as a solution
- Give a finite computable expression equal to operational capacity for every finite relay channel.
- Or prove a precise impossibility of the requested class of expressions and provide an exact alternative usable for every channel.
1Status
Current status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general. Exact unresolved remainder: No universal matching computable characterization was located.[1][2]
1Packet records
Recent contributions
Notes and companion material
Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general. Exact unresolved remainder: No universal matching computable characterization was located.
- Equivalent-formulation queries: general discrete memoryless relay channel capacity remains open 2026; relay channel exact capacity decode forward compress forward cut set
- Strongest checked neighboring result: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general.
- Exact unresolved remainder: No universal matching computable characterization was located.
How the 4 records connect
ProblemCapacity of the general discrete memoryless relay channel
All 3 recorded relations between these records and the problem
2See also
- A 368-word code in the fifth strong power of the 7-cycleinformation theory
- Optimal balanced-subset Mastermind on twelve pointsinformation theory
- Exact capacity region of the two-user Gaussian interference channelinformation theory
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Capacity of the general discrete memoryless relay channel.” TheoremDB. P3108. Problem statement; statement text SHA-256 658131a7d915b732d3b817fedec07209db46adc89b71750c3eadd8616cfad7af. https://theoremdb.org/statement/?ref=P3108
@misc{theoremdb-problem-658131a7d915b732d3b817fedec07209db46adc89b71750c3eadd8616cfad7af,
title = {{Capacity of the general discrete memoryless relay channel}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 658131a7d915b732d3b817fedec07209db46adc89b71750c3eadd8616cfad7af},
url = {https://theoremdb.org/statement/?ref=P3108}
}Plain text: Built Markdown snapshot
This problem includes 4 records joined by 3 typed links, sourced from doi.org[1], current as of August 1, 2026.
1References
- Packet source. T. Cover and A.E. Gamal, “Capacity theorems for the relay channel”. IEEE Transactions on Information Theory 25(5) (1979), 572-584. DOI 10.1109/TIT.1979.1056084. decode-forward, compress-forward, cut-set results. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Introduces the principal bounds and solves degraded and reverse-degraded cases.Also cited at T. Cover and A. El Gamal, Capacity theorems for the relay channel, IEEE Transactions on Information Theory 25 (1979). decode-forward, compress-forward, cut-set results.Source used to assess the problem's recorded status.For Capacity of the general discrete memoryless relay channel: This is the dated publication status for the canonical target Capacity of the general discrete memoryless relay channel.Source named by the research packet.
- Xiugang Wu, Leighton Pate Barnes, and Ayfer Ozgur, “"The Capacity of the Relay Channel": Solution to Cover's Problem in the Gaussian Case”. arXiv:1701.02043 (2017). abstract and main theorem. ↗preprint · primary source · arXiv:1701.02043, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Solves a major Gaussian special problem while distinguishing it from the general discrete memoryless capacity question.Source used to assess the problem's recorded status.For Capacity of the general discrete memoryless relay channel: Solves a major Gaussian special problem while distinguishing it from the general discrete memoryless capacity question.
Original TheoremDB editorial statement and source synthesis; external works are used for citation only.
Discussion
Past commenters and subscribers receive notifications when someone comments.