All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Time dependent complexity classes?

https://www.cshl.edu/the-difference-between-an-experts-brain-and-a-novices/ Has anyone formulated dynamical / time dependent complexity classes where the languages in the classes are not constant? I ...
23
votes
4answers
2k views

What evidence is there that Graph Isomorphism is not in $P$?

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete ...
0
votes
0answers
14 views

What are the steps and correct order of the operations in Machine Learning? [from Getting data to optimising models]

I've followed lots of tutorials on Machine Learning but in each of these, they go for a different strategy so it's quite confusing for me. I want to Know that what are the operations involved and what ...
2
votes
1answer
32 views

Term for a set that is not immune

At the outer bounds of computational complexity classes are those defined through computability theory (AKA recursion theory). This is where we get the well known complexity classes such as R, RE, and ...
0
votes
0answers
31 views

How do you prove the Nagarajan's Lemma? [on hold]

Let $H$ be a hypothesis class of multiclass predictors; namely, each $h\in H$ is a function from $X$ to $[k]$. Denote the Natarajan dimension of $H$ by $Ndim(H)$. Please prove the following lemma. $|...
-3
votes
0answers
28 views

Can postman-collection grammar be parsed? [on hold]

Think of postman-collection collection as a grammar. Goal: I am trying to parse the postman_echo collection json and persist the result into a new json copy on disk, resulting the same file as ...
6
votes
1answer
157 views

Constraints on sliding windows

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
3
votes
1answer
60 views

Is there a notion of “sequential” idempotence?

TL;DR: I have a definition, and I'm wondering if it already has a name or has been studied. Suppose we have a sequence of operations (or if we want to be mathematical, functions whose domains and ...
2
votes
0answers
23 views

Covering a set of moving points with two disks of same size

The best algorithms for the following problem has $O(n^2 \log{n})$ running time: Given a set $P$ of $n$ points in $\mathbb{R}^2$ and a real parameter $r$, can we cover all the points in $P$ with two ...
0
votes
0answers
103 views

Potentially stronger form of non-$ETH$

If we have a $2^{n^a}$ algorithm to $K$-$SAT$ where $a<1$ for all $K>2$ then $ETH$ fails and literature gives consequences. What are the consequences if $a=o(1)$?
-1
votes
0answers
26 views

tree decomposition elimination ordering

I already know how to find treewidth with elimination ordering on a tree. But how can I obtain an elimination ordering of width at most k from a tree decomposition of width k?
1
vote
2answers
63 views

Understanding non-equivalence of proof lengths according to proof systems

Here, in section 4.3, Fortnow says: But to prove P != NP we would need to show that tautologies cannot have short proofs in an arbitrary proof system. I am ...
3
votes
2answers
143 views

If $P=BPP$, then Is it correct that $IP=NP$?

This is my first question in this site. I ask this question since I got no comment and no answer for one year and two months in cs.stackexchange and it was automatically deleted by the system. So, ...
7
votes
2answers
824 views

Isn't it trivial to represent/reduce any classical physics problem in/to a Spin-Glass language which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
0
votes
0answers
43 views

Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
-1
votes
0answers
30 views

Time Complexity of STCONN in One-Tape Turing Machine

I couldn't successfully find relevant work in the time complexity of solving STCONN (in directed graph) in One-Tape Turing Machine. Of course there is a "linear-time" algorithm like DFS/BFS, but is ...
5
votes
0answers
82 views

Complexity of finding the largest induced subgraph with all even degrees

What is the complexity of the following problem? Instance: Simple, undirected graph $G$, and a positive integer $k$. Question: Does $G$ have an induced subgraph on at least $k$ vertices, such that ...
0
votes
2answers
128 views

Is the decidability of a language decidable? [on hold]

Is there a Turing machine that takes a language as input and decides/semi-decides if it is a decidable language? Comments + answer say trivially the answer is yes; however, I'm wondering here would ...
2
votes
0answers
66 views

Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
7
votes
1answer
614 views

Relationship between two graph optimization problems

Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph: P1. Find a largest induced subgraph of the ...
4
votes
0answers
88 views

Eliminating tautological axioms in tree-like $k$-DNF resolution

The propositional proof system $k$-DNF-resolution, a.k.a. $Res(k)$, is a generalization of propositional resolution, where the lines in a proof are $k$-DNF formulas, i.e., disjunctions of $k$-terms of ...
1
vote
3answers
305 views

what is a model of computation, mathematically? [closed]

Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't ...
3
votes
1answer
153 views

Are endmarkers necessary for Deterministic Pushdown Automata?

In the book by Kozen (Automata and Computability), the transition function of deterministic pushdown automata (DPDAs) is supposed, in contrast with non-deterministic pushdown automata (NPDAs), to ...
31
votes
3answers
1k views

Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
0
votes
0answers
84 views

Why P/poly can solve Unary halting problem while turing machine can't [closed]

My understanding: The unary halting problem is impossible for turing machine because it can’t decide n. P/poly can decide the Unary halting problem because, given An which accepts x if x = 1n and ...
-1
votes
0answers
33 views

Scheduling and routing

Given: $k > 1 $ sales execs, each specializing in one of 4 lines of business (LOBs), where each exec works (sales and travel) at 7.5 hours / day $n > 1$ client sites. Constraints: Each ...
-3
votes
0answers
61 views

Complexity theory in non-TM models and randomness and complete problems? [closed]

What are some of the non-TM models considered in complexity theory? How is randomness introduced in these models and what are the analogs of the SATISFIABILITY problem in these models?
-2
votes
0answers
40 views

Can Christofides algorithm provide different solution in different execution?

In symmetric TSP, is it possible to have several outputs for the execution of Christofides algorithm when all pairwise distances are different? If a number of pairwise distances are equal, is it ...
2
votes
1answer
117 views

What Is the Complexity of This Two-to-One Matching Problem?

Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V_1$ and $V_2$, where for all $v_1\in V_1$, we have $c(v_1)=1$ and for ...
2
votes
0answers
59 views

How hard is it to approximate distance of linear code

I'm trying to figure out what is the current knowledge about how hard it is, given a generating matrix of a linear code over a field $F_{q}$, approximate it's distance. I of course found that ...
3
votes
2answers
319 views

Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
-3
votes
0answers
26 views

Runtime of flood fill with multiple centres

What is the runtime if we are using the flood fill algorithm but with multiple centres from which it starts.
-1
votes
0answers
24 views

Approximation quality of a simple linearization of binary quadratic program

I am trying to linearize a binary quadratic program by a simple linear inequality i.e. for the given objective $\mathbf{\min_{x \in \{0,1\}^n} x^TAx}$, I want to linearize the objective by using ...
23
votes
2answers
797 views

Are shift-chains two-colorable?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ${\...
6
votes
1answer
109 views

SMT solving with less-than theory and monotonic functions

I am attempting to solve a less-than theory within an SMT paradigm that involves variables assigned to reals and assumes that all the functions used in the theory are monotonic. The theory's signature ...
-1
votes
1answer
48 views

Multivariable concave function $(n - 1) f(x) >= \sum_{i=1}^{n} f(x_{-i})$

Define the multi-dimension concave function $f(x): \mathbb{R}^n_+ \rightarrow \mathbb{R}_+$ where $x \in \mathbb{R}^n_+$, here I use $\mathbb{R}_+$ to represent the range $[0, \infty)$ and we let $f(\...
13
votes
1answer
4k views

What is the correct definition of $k$-tree?

As the title says, what is the correct definition of $k$-tree? There are several papers that talk about $k$-trees and partial $k$-trees as alternative definitions for graphs with bounded treewidth, ...
15
votes
1answer
583 views

Can one efficiently uniformly sample a neighbor of a vertex in the graph of a polytope?

I have a polytope $P$ defined by $\{ x : Ax \leq b, x \geq 0\}$ . Question: Given a vertex $v$ of $P$, is there a polynomial time algorithm to uniformly sample from the neighbors of $v$ in the graph ...
-4
votes
1answer
43 views

problem set for complexity problems [closed]

Identify set of problems which can be solved in polynomial time but if we change the constraints on those problems ...then these problems becomes np ( non- polynomial) hard problems.
3
votes
1answer
256 views

Complexity classes not closed under intersection and union

Some of the better known complexity classes: PP, NP, P... are closed under intersection and union. What are some counter-examples? Is there a natural reason for the common complexity classes to be ...
3
votes
0answers
64 views

Topologies for modelling divergence in the lambda-calculus

I wonder if there exist topologies for the lambda-calculus where computational divergence (like for $\Omega = (\lambda x. x x) (\lambda x. x x)$) has a topological meaning as the divergence of a ...
17
votes
1answer
2k views

Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
6
votes
1answer
169 views

Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?
-1
votes
0answers
61 views

Dependent type theory where branching information informs typing derivations?

In Extensional Martin-Löf type theory (extended with the necessary types) I don't believe the following is derivable $$ x:\mathbb{N},\,rep:\varPi n:\mathbb{N}.Vec\,n\ \vdash Rec_{\mathbb{B},b.Vec\, x}\...
0
votes
0answers
90 views

A Multiple Online Matching Problem?

1. Settings: There are $n$ clients. Each client $i$ has a budget of $B_i$ dollars. There are $P$ periods and each period contains $D$ days. Every client $i$ can make a bid $b_{ip}$ in period $p\in P$ ...
2
votes
0answers
148 views

How do computers check if two functions are the same?

To prove that two given functions are the same involves proving infinitely many statements. I wonder how to implement so that a computer can check such a statement? An easy example is the following: ...
2
votes
0answers
42 views

Church numerals and Kleene numerals

Church numerals $\overline{0} = \lambda fx. x$ and $\overline{n} = \lambda f x. f^n x$ are provisions for applying a function $n$ times to an argument. An alternate system of numerals, possibly ...
-1
votes
1answer
49 views

How to find for each 3-input boolean function the minimum number of NAND operators needed to compute it [closed]

I need to know for each of the $2^{2^3}$ boolean functions with $3$ inputs the smallest boolean circuit made only of NAND gates computing it (smallest in terms of the number gates). I would be glad ...
-4
votes
0answers
50 views

Can super computers solve Mega Chess Problems

mega chess problems: Dots represent number of pieces on a square. Think it as a kind of 3D chess. Think that pieces on a chess square can stay top of each other(only its own kind). You can move them ...
0
votes
0answers
51 views

What is the run-time of LP?

Are there any further generalizations known to the result about run-time of a LP than what is stated in Theorem 1 of these lecture notes, https://nisheethvishnoi.files.wordpress.com/2018/05/lecture71....

15 30 50 per page