[#P3108] Capacity of the general discrete memoryless relay channel
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.
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]
1Records
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
2See also
- Exact capacity region of the two-user Gaussian interference channelinformation theory
- Optimal balanced-subset Mastermind on twelve pointsinformation theory
- A 368-word code in the fifth strong power of the 7-cycleinformation theory
How to cite
TheoremDB contributors, “Capacity of the general discrete memoryless relay channel,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/general-relay-channel-capacityThis page as plain text: general-relay-channel-capacity.md
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.