c2b_default

TheoComp

asdf

asdf

18
0.0 (0)

Kartei Details

Karten 18
Sprache Deutsch
Kategorie Informatik
Stufe Grundschule
Erstellt / Aktualisiert 12.06.2025 / 13.06.2025
Weblink
https://card2brain.ch/box/20250612_theocomp
Einbinden
<iframe src="https://card2brain.ch/box/20250612_theocomp/embed" width="780" height="150" scrolling="no" frameborder="0"></iframe>
Lernen

Any infinite language is regular

Any finite language is regular

Any infinite language is not regular

The language \(\emptyset\) is regular

The language \(\emptyset\) is context-free

The language \(\{\epsilon\}\) is not regular

Any context-free language is regular

Any not-context free language is infinite

Any regular language is finite

Any context-free language is infinite

If a language L is regular, then L* is regular

If a Language L is regular, then \(\overline{L}\) is regular

Define P

Decision problems solvable by a deterministic Turing machine in polynomial time.

Define NP

Decision problems whose yes-instances can be verified in polynomial time by a deterministic Turing machine (equivalently, solvable in polynomial time by a nondeterministic Turing machine).

Define co-P

Decision problems whose no-instances are solvable by a deterministic Turing machine in polynomial time (i.e., complements of problems in P).
Note: Since P is closed under complement, co-P = P.

Define co-NP

Decision problems whose no-instances can be verified in polynomial time (complements of problems in NP).

Define NP-complete

Problems in NP that are at least as hard as every problem in NP:

  1. Membership: They themselves lie in NP.

  2. Hardness: Every NP problem reduces to them via a polynomial-time many-to-one reduction.
    If any NP-complete problem is solved in polynomial time, P = NP.

Define NP-hard

Problems at least as hard as the hardest problems in NP (every NP problem reduces to them), but not required to be in NP; they may be decision, optimization, or even non-decidable problems.

Lernen