Theorems 10.1 and 10.2 — Polynomial-Time Binary Encoding Reductions for Two-Agent Flow and Open Shops
ProvedTwoAgentSched.Shops.shops_encoding_reductioncomputational-complexityschedulingtwo-agent
Rescaling the flow shop construction by and the open shop construction by yields natural-number instances in and whose binary codes over are computable in polynomial time from .
Preamble
import Mathlib.Data.Real.Basic import Mathlib.Data.Fintype.Basic import Mathlib.Data.Fintype.Sum import Mathlib.Data.Finset.Max import Mathlib.Data.Finset.Sort import Mathlib.Data.Set.Card import Mathlib.Data.List.Sort import Mathlib.Tactic.Linarith import Mathlib.Tactic.Ring import Definitions.Def_TwoAgentSched_Shops_Construction
Formal statement
namespace TwoAgentSched.Shops
open CookPvsNP ProjSchedTW.Complexity
/-- Polynomial-time binary encoding reductions for Theorems 10.1 and 10.2 (Agnetis et al. 2004,
pp. 238–239): rescaling `flowInst p` by `2(k + 1)` and `openInst p` by `2` yields natural-number
shop instances whose binary codes in `flowLang` and `openLang` are computable in polynomial time
from `encNats p`. -/
theorem shops_encoding_reduction :
(∃ f : List BSym → List BSym, PolyTimeComputable f ∧
∀ x : List BSym,
((∃ p : List ℕ, Even p.sum ∧ (2 ≤ p.sum ∨ p.length ≤ 1) ∧
(flowInst p).FlowYes (flowQA p) (flowQB p) ∧ x = encNats p) ∨
(∃ p : List ℕ, p.sum = 0 ∧ x = encNats p)) ↔ f x ∈ flowLang) ∧
(∃ g : List BSym → List BSym, PolyTimeComputable g ∧
∀ x : List BSym,
(∃ p : List ℕ, (openInst p).OpenYes (openQA p) (openQB p) ∧ x = encNats p) ↔
g x ∈ openLang) := by sorry
end TwoAgentSched.ShopsSource
Agnetis, Mirchandani, Pacciarelli & Pacifici 2004, Scheduling problems with two competing agents, Operations Research 52(2), pp. 238–239, Theorems 10.1 and 10.2