会员服务
TR · 包含 · CAP · 相同 · 潜在 ·
12 月 25 日
A Note on Avoid vs MCSP
翻译：关于Avoid与MCSP问题的注记
Edward A. Hirsch,Ilya Volkovich
Edward A. Hirsch,Ilya Volkovich

A recent result of Ghentiyala, Li, and Stephens-Davidowitz (ECCC TR 25-210) shows that any language reducible to the Range Avoidance Problem via deterministic or randomized Turing reductions is contained in AM $\cap$ coAM. In this note, we present a different potential avenue for obtaining the same result via the Minimal Circuit Size Problem.


翻译：Ghentiyala、Li和Stephens-Davidowitz（ECCC TR 25-210）的最新结果表明，任何通过确定性或随机图灵归约可化为范围规避问题的语言均包含于AM $\cap$ coAM中。本文提出一种通过最小电路规模问题获得相同结论的潜在新路径。
0
下载
关闭预览

相关内容

TR：IEEE Transactions on Robotics Explanation： Publisher：IEEE。 SIT： http://dblp.uni-trier.de/db/journals/trob/
【SIGIR2020-中科院计算所】L2R2: 利用排名进行外展推理，L2R2: Leveraging Ranking for Abductive Reasoning
【SIGIR2020-中科院计算所】L2R2: 利用排名进行外展推理，L2R2: Leveraging Ranking for Abductive Reasoning
专知会员服务
11+阅读 · 2020年5月25日
语义相似性算法演化论文，29页pdf，Evolution of Semantic Similarity - A Survey
语义相似性算法演化论文，29页pdf，Evolution of Semantic Similarity - A Survey
专知会员服务
44+阅读 · 2020年4月30日
【IJCAI2020】统计相关模型，A Complete Characterization of Projectivity for Statistical Relational Models
【IJCAI2020】统计相关模型，A Complete Characterization of Projectivity for Statistical Relational Models
专知会员服务
20+阅读 · 2020年4月25日
基于动态时空图CNNs的交通流预测，Dynamic Spatio-temporal Graph-based CNNs for Traffic Flow Prediction
基于动态时空图CNNs的交通流预测，Dynamic Spatio-temporal Graph-based CNNs for Traffic Flow Prediction
专知会员服务
136+阅读 · 2020年3月8日
【NeurIPS2019】图变换网络：Graph Transformer Network
【NeurIPS2019】图变换网络：Graph Transformer Network
专知会员服务
112+阅读 · 2019年11月25日
AAAI 2022 | ProtGNN：自解释图神经网络
AAAI 2022 | ProtGNN：自解释图神经网络
专知
10+阅读 · 2022年2月28日
【ICML2021】因果匹配领域泛化
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
【KDD2020-Tutorial】因果推理与稳定学习，Causal Inference and Stable Learning
【KDD2020-Tutorial】因果推理与稳定学习，Causal Inference and Stable Learning
专知
11+阅读 · 2020年8月28日
【NeurIPS2019】图变换网络：Graph Transformer Network
【NeurIPS2019】图变换网络：Graph Transformer Network
专知
245+阅读 · 2019年11月18日
Single-Shot Object Detection with Enriched Semantics
Single-Shot Object Detection with Enriched Semantics
统计学习与视觉计算组
14+阅读 · 2018年8月29日
半线性广义Tricomi方程Cauchy问题解的生命跨度估计研究
国家自然科学基金
0+阅读 · 2017年12月31日
Hamilton-Jacibi方程的弱KAM理论
国家自然科学基金
2+阅读 · 2017年12月31日
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
2+阅读 · 2015年12月31日
L-函数、大值特征和及相关问题研究
国家自然科学基金
0+阅读 · 2014年12月31日
Poisson流形上的修正Hamilton方法
国家自然科学基金
0+阅读 · 2014年12月31日
Atom of Thoughts for Markov LLM Test-Time Scaling
Arxiv
0+阅读 · 12月27日
A Note on the NP-Hardness of PARTITION Via First-Order Projections
Arxiv
0+阅读 · 12月24日
Generalization of RLVR Using Causal Reasoning as a Testbed
Arxiv
0+阅读 · 12月23日
Solomonoff-Inspired Hypothesis Ranking with LLMs for Prediction Under Uncertainty
Arxiv
0+阅读 · 12月22日
Accuracy of Uniform Inference on Fine Grid Points
Arxiv
0+阅读 · 12月21日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
TR
包含
CAP
相同
潜在
相关VIP内容
【SIGIR2020-中科院计算所】L2R2: 利用排名进行外展推理，L2R2: Leveraging Ranking for Abductive Reasoning
【SIGIR2020-中科院计算所】L2R2: 利用排名进行外展推理，L2R2: Leveraging Ranking for Abductive Reasoning
专知会员服务
11+阅读 · 2020年5月25日
语义相似性算法演化论文，29页pdf，Evolution of Semantic Similarity - A Survey
语义相似性算法演化论文，29页pdf，Evolution of Semantic Similarity - A Survey
专知会员服务
44+阅读 · 2020年4月30日
【IJCAI2020】统计相关模型，A Complete Characterization of Projectivity for Statistical Relational Models
【IJCAI2020】统计相关模型，A Complete Characterization of Projectivity for Statistical Relational Models
专知会员服务
20+阅读 · 2020年4月25日
基于动态时空图CNNs的交通流预测，Dynamic Spatio-temporal Graph-based CNNs for Traffic Flow Prediction
基于动态时空图CNNs的交通流预测，Dynamic Spatio-temporal Graph-based CNNs for Traffic Flow Prediction
专知会员服务
136+阅读 · 2020年3月8日
【NeurIPS2019】图变换网络：Graph Transformer Network
【NeurIPS2019】图变换网络：Graph Transformer Network
专知会员服务
112+阅读 · 2019年11月25日
热门VIP内容
相关资讯
AAAI 2022 | ProtGNN：自解释图神经网络
AAAI 2022 | ProtGNN：自解释图神经网络
专知
10+阅读 · 2022年2月28日
【ICML2021】因果匹配领域泛化
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
【KDD2020-Tutorial】因果推理与稳定学习，Causal Inference and Stable Learning
【KDD2020-Tutorial】因果推理与稳定学习，Causal Inference and Stable Learning
专知
11+阅读 · 2020年8月28日
【NeurIPS2019】图变换网络：Graph Transformer Network
【NeurIPS2019】图变换网络：Graph Transformer Network
专知
245+阅读 · 2019年11月18日
Single-Shot Object Detection with Enriched Semantics
Single-Shot Object Detection with Enriched Semantics
统计学习与视觉计算组
14+阅读 · 2018年8月29日
相关论文
Atom of Thoughts for Markov LLM Test-Time Scaling
Arxiv
0+阅读 · 12月27日
A Note on the NP-Hardness of PARTITION Via First-Order Projections
Arxiv
0+阅读 · 12月24日
Generalization of RLVR Using Causal Reasoning as a Testbed
Arxiv
0+阅读 · 12月23日
Solomonoff-Inspired Hypothesis Ranking with LLMs for Prediction Under Uncertainty
Arxiv
0+阅读 · 12月22日
Accuracy of Uniform Inference on Fine Grid Points
Arxiv
0+阅读 · 12月21日
相关基金
半线性广义Tricomi方程Cauchy问题解的生命跨度估计研究
国家自然科学基金
0+阅读 · 2017年12月31日
Hamilton-Jacibi方程的弱KAM理论
国家自然科学基金
2+阅读 · 2017年12月31日
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
2+阅读 · 2015年12月31日
L-函数、大值特征和及相关问题研究
国家自然科学基金
0+阅读 · 2014年12月31日
Poisson流形上的修正Hamilton方法
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员
Top