We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph isomorphic to G? 2. Given a countable graph H that has a(n induced) subgraph isomorphic to G, find such a subgraph. The framework for our investigations is given by effective Wadge reducibility and by Weihrauch reducibility. Our work follows on "Reverse mathematics and Weihrauch analysis motivated by finite complexity theory" (Computability, 2021) by BeMent, Hirst and Wallace, and we answer several of their open questions.
翻译：我们研究与一个固定可数图 G 相关的以下有关计算任务的复杂性：1. 作为输入提供的可数图 H 是否有一个同构于 G 的（诱导）子图？2. 给定一个含有同构于 G 的（诱导）子图的可数图 H，找到这样的子图。我们的研究框架为有效的 Wadge 可简化和 Weihrauch 可简化。我们的工作基于 BeMent、Hirst and Wallace 的“Reverse mathematics and Weihrauch analysis motivated by finite complexity theory”（Computability，2021），并回答了他们的几个开放问题。
相关内容
微信扫码咨询专知VIP会员