理論計算機科学

理論的なコンピューター科学者および関連分野の研究者向けのQ＆A

-5
数学的証明自体はNP困難ですか？
this videoの8時のマークで、彼は物事を証明すること自体がNPの問題であると主張しています。私はこれについてもっと洞察を求めています。誰かがこの概念を私に説明するのを手伝ってくれたり、さらにいくつかの参考文献...
cc.complexity-theory np-hardness complexity-classes proof-complexity 
5
Hポリトープの結合を3次元で計算する複雑さ
$ \ mathbb {R} ^ 3 $のポリトープのセット $ P_1、\ ldots、P_k $ を検討してください、それぞれ、半空間と有理法線の交差として与えられます（特に、それらはすべて凸です）。ターゲットのポリトープ $ Q $ も与えられます。これ...
reference-request computational-geometry convex-geometry 
10
囲碁の理論的な複雑さ-最先端の技術
Goの理論的な複雑さの最新の進歩は何ですか？囲碁の複雑さに関する初期の作品をいくつか知っています： Go is polynomial-space hard は、GoがPSPACEハードであることを証明しました。 Ladders are PSPACE-complete は、はしごがPSPACE完全...
complexity-classes gt.game-theory complexity 
7
PCP定理の最初の証明で使用された曲線に関する技術的補題
hereからの証明を読んでいて、正しくないように見える技術的補題を見つけました（その証明は短くて非常にあいまいです）。これはかなり具体的で、状況に問題があることはわかっていますが、自分ではそれを理解できま...
cc.complexity-theory algebra pcp 
6
$ L \ neq NL $のとき、$ L \ subset 1NL $ですか？
ログスペースチューリングマシンには、読み取り専用の入力テープと書き込み専用の出力テープがあり、最大で $ O（\ log n）$ のスペースを使用しますその読み書きワークテープで。クラス $ L $ および $ NL $ には、確定的ま...
cc.complexity-theory complexity-classes turing-machines nondeterminism space-complexity 
2
FO（TC）下限ゲーム？
$ FO（TC）$ の式に下限のある方法論を提供するゲーム/代数構造を知っている人はいますか？EFゲームは一次および二次ステートメントに適用されるので承知していますが、 $ FO（TC）$ の下限を決定できるようにしたいと考え...
cc.complexity-theory lo.logic finite-model-theory 
0
NP完全グラフの問題/プロパティのリスト？
グラフとネットワークに関するさまざまな意思決定問題を見つけるための優れた情報源はありますか？私がやっているプロジェクトでは、さまざまな問題をたくさん見ることができると便利です。それらを見つけるための良...
graph-theory np 
1
拡張型理論と機能拡張性
機能拡張の原則です $（\ forall x。f（x）= g（x））\ implies f = g $ 、ETTから導出可能？特に、これは公理Kを使用してAgdaで導出できますか？...
type-theory automated-theorem-proving agda 
3
コルモゴロフ2つの計算可能な関数の合成の複雑さ
2つの計算可能な関数 $ f $ と $ g $ をバイナリ文字列としてエンコードするとしましょう。 $ f、g \ in \ {0,1 \} ^ * $ 。私が気になるのは、以下の上限と下限を見つけることができるかどうかです。 \ begin {equation}K（f \ circ g）\ tag...
reference-request kolmogorov-complexity 
3
凸ポリゴンの包含関係
次の問題があり、私が行っていた一部の作業で副問題として発生し、完全に行き詰まっています。ワーストケースの時間の複雑さの点でのみ興味があることに注意してください（ヒューリスティックなどではありません）。...
ds.algorithms computational-geometry polygon convex-hull 
5
ファンクタの厳密な陽性の意味論的定義
再帰型の定義を次のように考える場合：F : Type -> Type; T = fix F; 再帰子が終了しないようにするには、関数Fが正または厳密に正である必要があることについて話し合うのが慣習です。私は厳密な陽性の通常の構文定義に精通...
type-theory 
-2
最小の頂点カバーと奇数サイクル
奇数サイクルのないグラフ G があるとします。線形計画問題として定式化された G の最小頂点カバー問題を考えます。つまり、各頂点 $ v_ {i} $ について、変数 $ x_ {i} $ 、各エッジ $ v_ {i} v_ {j} $ について制約 $ x_ {i} + x_ {j} \ ge...
graph-theory graph-algorithms 
1
埋め込まれた単体の複合体のデータ構造
$ \に埋め込んだ $ n $ 次元の単体複合体をエンコードするデータ構造を探していますmathbb {R} ^ {n + 1} $ 。平面グラフの回転システムを一般化するcombinatorial mapsと、方向付け不能を可能にするために組み合わせマップをさらに...
ds.data-structures computational-geometry topology 
3
免疫がないセットの用語
計算の複雑さのクラスの外側の境界は、計算可能性理論（AKA再帰理論）によって定義されたものです。ここで、R、RE、co-REなどのよく知られた複雑度クラスを取得します。ただし、計算可能性理論によって定義される別のも...
complexity-classes fl.formal-languages 
1
すべての多項式ランタイムの帰納？
これまで $ \ mathrm {P} $ に言語がないことを証明するための証明テクニックはありませんでした。言語が $ \ mathrm {TIME}（n ^ k）$ にあるspan class = math-container > $ k $ ？例： $ L \ notin \ mathrm {TIME}（n ^ 0）$ 、 $ L \ notin \ mathrm {TIME}（n ...
time-complexity polynomial-time 
2
複雑さが不明な最大サブグラフ問題
$ Q $ を多項式時間決定可能グラフプロパティにしましょう。グラフで、部分グラフ $ S $ を $ Q $ -subgraph、 $ S $ にプ​​ロパティ $ Q $ がある場合。次の最適化問題を検討してください。 最大 $ Q $ -サブグラフの問題 入力：単...
cc.complexity-theory graph-theory graph-algorithms np-complete 
4
特別号に会議論文（SODAなど）を招待する基準は何ですか？
これは主に、私が書き込もうとしている一部の移民関連文書であり、SODA会議の特別な問題のために選ばれた少数の論文のみが招待されていることを言及するオンラインリンクを参照したいと考えています。また、選択基準...
soft-question conferences journals 

Next page