Lax Lean Archive

The encoding of crawling instances is faithful and size-honest

Lax117614.CrawlEncoding · concepts/Lax117614/CrawlEncoding.lean · lax-117614

proven

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this concept may be incorrect.

No flags have been submitted.

    Community review

    Flag this concept

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    No source line selected.

    Natural Language Statement

    Theorem

    A packaged crawling instance has a crawl within budget exactly when the website graph it encodes is a yes-instance of the graph crawling problem; the encoded website graph has at most as many pages as the size of the instance; and the size of the instance is at most 4(n+2)24(n+2)^2 for n+1n+1 pages. The encoding neither pads nor compresses.

    Concept map
    10 concepts
    100%
    Proven claimDefinitionThis conceptRelated conceptA → B: B builds on A
    Evidence

    This concept declares 3 statements. Each proof establishes one of them relative to its assumptions.

    1 crawlEncoding_faithful proven

    2 crawlSize_ge_card proven

    3 crawlSize_le_card proven

    Lean source view on GitHub

    1import Lax117614.WebsiteGraphs
    2import Lax117614.GraphCrawlingProblem
    3import Lax117614.CrawlInstances
    4
    5/-!
    6---
    7title: The encoding of crawling instances is faithful and size-honest
    8type: theorem
    9---
    10A packaged crawling instance has a crawl within budget exactly when the
    11website graph it encodes is a yes-instance of the graph crawling problem;
    12the encoded website graph has at most as many pages as the size of the
    13instance; and the size of the instance is at most 4(n+2)24(n+2)^2 for n+1n+1
    14pages. The encoding neither pads nor compresses.
    15-/
    16
    17namespace Lax117614.CrawlEncoding
    18
    19open FirstOrder FirstOrder.Language Structure
    20open Lax117614.WebsiteGraphs Lax117614.GraphCrawlingProblem Lax117614.CrawlInstances
    21
    22/-- The encoding is faithful: a packaged instance has a crawl within budget
    23exactly when the website graph it encodes is a yes-instance of
    24GraphCrawling. -/
    25axiom crawlEncoding_faithful : ∀ i : CrawlInstance,
    26 ConcreteCrawlHolds i ↔ GraphCrawling (Fin (i.n + 1))
    27
    28/-- No padding: the encoded structure has at most as many elements as the
    29textbook size of the instance. -/
    30axiom crawlSize_ge_card : ∀ i : CrawlInstance, i.n + 1 ≤ crawlSize i
    31
    32/-- No compression: the textbook size of an instance is polynomial in the
    33number of elements of the encoded structure. -/
    34axiom crawlSize_le_card : ∀ i : CrawlInstance, crawlSize i ≤ 4 * (i.n + 2) ^ 2
    35
    36end Lax117614.CrawlEncoding
    37
    Show ProofShow ProofShow Proof
    Builds on
    Used by

    none

    From Mathlib

    none

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above.

    Loading discussion…