The catalog

All problems

Every statement in the catalog, readable in place. Filters apply instantly; search covers names, IDs, and the LaTeX statements themselves.

Showing 20 of 280 problems in Logic and foundations

NT-TRANS-021

Schanuel’s Conjecture

LandmarkConjecturec. 1960

For every integer

n \geq 1

, if

z_{1}, \dots, z_{n} \in C

are linearly independent over

Q

, then

trdeg_{Q} Q (z_{1}, \dots, z_{n}, e^{z_{1}}, \dots, e^{z_{n}}) \geq n,

where

trdeg_{Q}

denotes transcendence degree over

Q

NT-LOGIC-025

Hilbert’s Tenth Problem over $\mathbb Q$

LandmarkOpen problem1970

There is no Turing machine which, on every input polynomial

f \in Z [x_{1}, \dots, x_{n}]

(where

n

is part of the input), halts and correctly decides whether there exists

(q_{1}, \dots, q_{n}) \in Q^{n}

with

f (q_{1}, \dots, q_{n}) = 0

ALG-GROUP-021

Soficity Conjecture

LandmarkConjecture2000

Every countable group is sofic. Explicitly, for every countable group

G

, finite

F \subseteq G

, and

ε > 0

, there are an integer

n

and a map

σ : G \to Sym (n)

such that

σ (1) = 1

d_{H} (σ (g h), σ (g) σ (h)) < ε (g, h \in F),

and

d_{H} (σ (g), 1) > 1 - ε

for every

g \in F ∖ {1}

, where

d_{H}

is normalized Hamming distance.

ALG-GROUP-015

Boone–Higman Conjecture

MajorConjecture1974

Every finitely generated group with solvable word problem embeds into a finitely presented simple group.

ANAL-FA-020

Hyperlinear Group Conjecture

MajorConjecturec. 2000

Every countable group

G

is hyperlinear: there are integers

n_{k}

and an injective homomorphism

G ⟶ k \prod U (n_{k}) / k ⨁ U (n_{k}),

where the metric ultraproduct uses normalized Hilbert--Schmidt distance and a nonprincipal ultrafilter.

TCS-001

$P$ versus $NP$

IconicOpen problem1971

P \neq = NP ?

Here

P

is the class of decision languages recognized by deterministic Turing machines in polynomial time, and

NP

is the class recognized by nondeterministic Turing machines in polynomial time (equivalently, languages with polynomial-size certificates verifiable in deterministic polynomial time).

TCS-002

$NP$ versus $coNP$

LandmarkOpen problemc. 1971

NP \neq = co NP,

where

NP

is nondeterministic polynomial time,

\overline{L} = {0, 1}^{*} ∖ L

, and

co NP = {L : \overline{L} \in NP}

TCS-003

$L$ versus $NL$

LandmarkOpen problemc. 1970

L \neq = N L ?

Here

L

and

N L

are the languages decidable by, respectively, deterministic and nondeterministic Turing machines using

O (lo g n)

work-tape cells on inputs of length

n

, with read-only input.

TCS-006

$NP\nsubseteq P/poly$

MajorConjecturec. 1980

There is a language in

NP

that is not decided by any family

(C_{n})_{n \geq 1}

of Boolean circuits of size polynomial in

n

, where

C_{n}

decides membership for all inputs of length

n

; in symbols,

NP ⊈ P / p o l y .

Here

NP

is nondeterministic polynomial time, and

P / p o l y

is the class defined by such polynomial-size, nonuniform circuit families.

TCS-017

Berman–Hartmanis Isomorphism Conjecture

MajorConjecture1977

A, B \subseteq {0, 1}^{*}

are both

NP

-complete, where

NP

is nondeterministic polynomial time, and completeness is under polynomial-time many-one reductions, then there exists a bijection

f : {0, 1}^{*} \to {0, 1}^{*}

such that

f

and

f^{- 1}

are polynomial-time computable and

x \in A ⟺ f (x) \in B .

TCS-025

NP-Hardness of the Minimum Circuit Size Problem

MajorOpen problemc. 1975

The Minimum Circuit Size Problem (MCSP) takes as input the

N = 2^{n}

-bit truth table of a Boolean function

f : {0, 1}^{n} \to {0, 1}

and an integer

s \leq N

, and asks whether

f

has a Boolean circuit over the fixed complete basis

{AND, OR, NOT}

, with

AND

and

OR

of fan-in two, and with at most

s

gates. Is MCSP

NP

-hard under deterministic polynomial-time many-one reductions?

LOG-MODEL-001

Vaught Conjecture

LandmarkConjecture1961

Let

L

be a countable first-order language and

T

a complete

L

-theory. The number

I (T, ℵ_{0})

of isomorphism classes of countable models of

T

is either at most countable or exactly

2^{ℵ_{0}}

LOG-DEC-005

Decidability of the Real Exponential Field

LandmarkOpen problemc. 1950

There exists an algorithm which, given any first-order sentence

φ

in the language

{0, 1, +, \cdot, <, exp}

, halts and correctly decides whether

(R; 0, 1, +, \cdot, <, x \mapsto e^{x}) ⊨ φ .

LOG-INF-006

Shelah’s Categoricity Conjecture for $L_{\omega_1,\omega}$

LandmarkConjecturec. 1977

Let

ψ

be a sentence of the countable infinitary logic

L_{ω_{1}, ω}

, which permits countable conjunctions and disjunctions but only finite strings of quantifiers. If

ψ

has, up to isomorphism, exactly one model of some cardinality

λ \geq ℶ_{ω_{1}}

, then it has exactly one model of every cardinality

μ \geq ℶ_{ω_{1}}

, where

ℶ_{0} = ℵ_{0}

ℶ_{α + 1} = 2^{ℶ_{α}}

, and

ℶ_{λ} = sup_{α < λ} ℶ_{α}

at limit ordinals.

LOG-SET-007

HOD Conjecture

LandmarkConjecturec. 2010

Assume there is an extendible cardinal, meaning a cardinal

δ

such that for every ordinal

λ > δ

there are an ordinal

θ

and an elementary embedding

j : V_{λ} \to V_{θ}

with critical point

δ

and

j (δ) > λ

. Then there is a proper class of regular cardinals

κ

that are not

ω

-strongly measurable in

HOD

. Here

HOD

is the class of hereditarily ordinal-definable sets, and a regular

κ

ω

-strongly measurable in

HOD

if there is

η < κ

with

(2^{η})^{HOD} < κ

such that

HOD

has no partition of

S_{ω}^{κ} = {α < κ : cf (α) = ω}

into

η

stationary sets.

LOG-MODEL-002

Cherlin–Zilber Algebraicity Conjecture

MajorConjecturec. 1979

Every infinite simple group

G

of finite Morley rank is, as an abstract group, isomorphic to the group of

K

-rational points of a simple algebraic group over an algebraically closed field

K

LOG-MODEL-003

Stable Fields Conjecture

MajorConjecturec. 1971

K

is an infinite field whose complete first-order theory in the language of rings is stable, then

K

is separably closed.

LOG-MODEL-004

NIP Fields Conjecture

MajorConjecturec. 2015

Let

K

be an infinite field whose complete first-order theory in the language of rings has no independence property (is NIP). Then at least one of the following holds:

K

is separably closed;

K

is real closed; or

K

admits a nontrivial henselian valuation.

LOG-COMP-008

Martin’s Conjecture for Borel Turing-Invariant Functions

MajorConjecturec. 1978

Let

2^{ω}

be the set of subsets of

N

, identified with the reals, and let

\leq_{T}

\equiv_{T}

, and

x^{'}

denote Turing reducibility, Turing equivalence, and the Turing jump. A map

f : 2^{ω} \to 2^{ω}

is Turing-invariant if

x \equiv_{T} y

implies

f (x) \equiv_{T} f (y)

. A Turing cone is a set

C_{z} = {x : z \leq_{T} x}

. For Borel Turing-invariant maps define

f \leq_{M} g ⟺ (\exists z) (\forall x \in C_{z}) f (x) \leq_{T} g (x),

and write

f \equiv_{M} g

when both

f \leq_{M} g

and

g \leq_{M} f

. Then: 1. Every Borel Turing-invariant

f

is either constant in Turing degree on a cone, or

id \leq_{M} f

. 2. The quotient by

\equiv_{M}

of the maps satisfying

id \leq_{M} f

is well-ordered by

\leq_{M}

, and the immediate successor of

[f]

is represented by

x \mapsto f (x)^{'}

LOG-SET-009

Reinhardt Cardinal Inconsistency Problem

MajorOpen problem1967

Prove in

ZF

, without the axiom of choice, that there is no nontrivial elementary embedding

j : V \to V

. Equivalently, determine whether the existence of a Reinhardt cardinal, the critical point of such an embedding, is inconsistent with

ZF