matrix_ctc_000_V1
收藏matrix_ctc_000_V1 数据集概述
基本信息
- 数据集名称: matrix_ctc_000_V1
- 提供商: Matrix Solutions LLC
- 类别: Science
- 订阅者数量: 1
- API版本: v1 (current)
- 访问级别: BASIC (Tier based)
核心功能
该服务围绕一个核心理念构建：许多困难的组合问题存在于NP领域，而更丰富的约束和类游戏结构通常位于PSPACE及相关类别中。引擎将结构化问题实例简化为一个共同的逻辑核心，并以受控、资源受限的方式搜索该核心——我们将其描述为模拟时空工程：将计算展开的“位置和时间”（编码布局、变量排序和搜索几何）视为设计的一部分，类似于在可能性的受限时空中塑造路径。
这是一个旨在通过使用时空工程（或模拟时空工程）解决NP问题（特别是在PSPACE领域）的脚本。
技术描述
- matrix_ctc_000 — NP → CNF → SAT + Deutsch-CTC feed: 经典的穷举式SAT求解器，具有来自常见NP完全问题的多项式时间归约和一条**Cook–Levin（电路）**路径。输出一个JSON Deutsch-CTC feed (
deutsch_ctc_feed)，供下游量子/CTC工具使用。 - 该仓库不运行完整的Deutsch-CTC量子堆栈；它以稳定的格式准备CNF + SAT结果。
服务API：请求、响应和问题类型
所有求解器通信都是每个请求一个JSON对象。规范的入口点包括：
app/solve.py— stdin 或--json-file→ stdout JSON。app/lambda_handler.py— HTTP正文中的相同负载（Lambda / Function URL / API Gateway）。
响应信封
成功处理返回一个以下形式的对象： json { "type": "<problem_type>", "ok": true, "solution": { }, "counts": { } }
失败时，HTTP层可能返回API Gateway形状的错误；在本地，solve.py将身份验证或解析错误打印到stderr。
环境限制
| 变量 | 含义 |
|---|---|
NP_SOLVER_MAX_VARS |
穷举SAT的最大变量数（默认24）。增加它会将最坏情况下的工作量增加到2^n。 |
NP_SOLVER_MAX_REDUCTION_CLAUSES |
归约期间生成的CNF大小的可选上限（参见np_reduce用法）。 |
构建输入：type字段
每个负载必须包含**"type": "<name>"**。支持的名称和形状包括：
sat 或 cnf
经典的CNF可满足性（Cook-Levin通用目标）。
-
选项A — 显式子句（变量
1 … n_vars；文字是[-n_vars, -1] ∪ [1, n_vars]中的非零整数）： json { "type": "sat", "n_vars": 3, "clauses": [[1, 2], [-1, -2, 3]] } -
选项B — DIMACS字符串在
dimacs中（代替n_vars/clauses）。
3sat
与sat相同的文字约定；通常每个内部列表的长度≤3（由您的数据强制执行，不严格验证仅为3-SAT）：
json
{
"type": "3sat",
"n_vars": 4,
"clauses": [[1, 2, 3], [-1, 2, -3]]
}
subset_sum
决策：是否存在nums的一个子集，其和为target？
json
{
"type": "subset_sum",
"nums": [3, 5, 7, 11],
"target": 16
}
vertex_cover
参数：图大小n，预算k，无向边[u, v]，顶点从0开始。
json
{
"type": "vertex_cover",
"n": 5,
"k": 2,
"edges": [[0, 1], [1, 2], [2, 3]]
}
3_color
图在n个顶点上，边同上；3种颜色。
json
{
"type": "3_color",
"n": 4,
"edges": [[0, 1], [1, 2], [2, 3]]
}
max_clique
邻接矩阵adj（n×n，对称），1 = 边。求解器通过重复的决策调用搜索最大团（在密集图上可能很重）。
json
{
"type": "max_clique",
"adj": [
[0, 1, 0],
[1, 0, 1],
[0, 1, 0]
]
}
reduce（通用归约钩子）
在**instance上运行指定的归约from_problem**，然后进行SAT求解（除非solve: false）。可选：include_cnf，solve。
支持的**from_problem**值（参见np_reduce.reduce_to_sat）：
from_problem |
instance形状（摘要） |
|---|---|
vertex_cover |
n, k, edges |
independent_set |
n, k, edges |
clique |
n, k, edges |
k_color, 3_color, graph_coloring |
n, edges, k_colors（3_color默认为3） |
subset_sum |
nums, target |
circuit_verifier（别名：cook_levin_circuit, …） |
布尔电路：max_wire, fixed, witness_wires, gates, output_wire — 参见np_reduce.circuit_verifier_to_sat |
示例（顶点覆盖作为归约）： json { "type": "reduce", "from_problem": "vertex_cover", "instance": { "n": 3, "k": 2, "edges": [[0, 1], [1, 2], [0, 2]] }, "solve": true }
示例（电路验证器 — 高级）： json { "type": "reduce", "from_problem": "circuit_verifier", "instance": { "max_wire": 4, "fixed": { "3": 0 }, "witness_wires": [1, 2], "gates": [{ "out": 4, "op": "and", "in": [1, 2] }], "output_wire": 4 } }
我们可以“解决”哪些问题？
在复杂性理论术语中，引擎通过将结构化NP问题归约为CNF并运行穷举SAT过程（sat_cnf）来决定实例。这对于NP_SOLVER_MAX_VARS内的小型和中型实例是合适的。它不为任意的NP-hard输入提供多项式时间的精确算法。
实际支持的系列（通过type或reduce）：
- SAT / CNF（包括DIMACS-in-JSON）。
- 3-SAT作为同一引擎上的便捷路径。
- 子集和、顶点覆盖、3着色、最大团（在
np_api/np_reduce中实现）。 - 通过
type: "reduce"和**circuit_verifier进行自定义归约**，用于小型验证器电路。
项目结构
| 路径 | 用途 |
|---|---|
app/src/ |
np_reduce, np_api, np_targets（qsg.py targets的目录） |
app/solve.py |
JSON输入 → JSON输出 |
app/pipeline_dctc.py |
相同的求解器 + deutsch_ctc_feed包装器（schema_version: matrix_ctc_dctc_feed_v1） |
qsg.py |
精简启动器：targets, solve, pipeline |
app/lambda_handler.py |
AWS Lambda处理程序（np_api.solve）；与docker/Dockerfile.lambda一起使用 |
docker/ |
Dockerfile（强化）, Dockerfile.lambda（ECR → Lambda）, ECR_LAMBDA.md, compose |
scripts/ |
build.*, push-ecr.*, verify_targets.py, verify_reduction_soundness.py |
快速开始（本地）
bash set PYTHONPATH=appsrc python qsg.py targets echo {"type":"sat","n_vars":2,"clauses":[[1,2],[-1,-2]]} | python appsolve.py python qsg.py pipeline --expr "x0 & w0" --instance-bits x0=1
同一管道中的归约器（stdin JSON → CNF在deutsch_ctc_feed中 + 可选的Deutsch-CTC元数据）：
bash
python -c "import json; print(json.dumps({type:reduce,from_problem:vertex_cover,instance:{n:3,k:2,edges:[[0,1],[1,2],[0,2]]}}))" | python apppipeline_dctc.py --deutsch-ctc
（--dctc是--deutsch-ctc的别名。）
入口点
| 入口 | 角色 |
|---|---|
app/solve.py |
JSON输入 → JSON输出（一个请求） |
app/pipeline_dctc.py |
添加deutsch_ctc_feed包装器 |
qsg.py |
targets |
环境
NP_SOLVER_MAX_VARS— 穷举SAT搜索宽度的上限（默认24）。NP_SOLVER_MAX_REDUCTION_CLAUSES— 生成的CNF大小的上限。
