# P3108: Capacity of the general discrete memoryless relay channel

- ID: `P3108`
- Reference: `general-relay-channel-capacity`
- Page: https://theoremdb.org/statements/P3108
- Record maturity: Reviewed problem with recorded work

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

### Context

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.

### Problem setup

- **Definition (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 (capacity).** The largest reliable source-to-destination communication rate.
- **Remark.** 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.

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

## 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. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general.

The exact unresolved remainder is: No universal matching computable characterization was located.

A complete resolution must meet the following acceptance conditions:
- 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.

### Background and intake notes

- 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.
- The release review checked 2 structured sources on 2026-08-01.
- 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.

### Other known results

- **Claim 2** (supported): Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: Exact capacity is known for degraded and other subclasses; broad inner and outer bounds remain separated in general. Unresolved remainder: No universal matching computable characterization was located. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): No universal matching computable characterization was located.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `general-relay-channel-capacity`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://doi.org/10.1109/TIT.1979.1056084
   - 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
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Introduces the principal bounds and solves degraded and reverse-degraded cases.
   - 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.
2. <a id="reference-2"></a>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 https://arxiv.org/abs/1701.02043
   - preprint; primary source; arXiv:1701.02043, checked 2026-08-01; checked 2026-08-01
   - Source 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.