9
EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof. Here's the ...
5
Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$):
Let $h_1,\ldots,h_n$ be an enumeration of all the bounding hyperplanes of the
polytopes $P_1,\ldots,P_k$ and $Q$.
Compute the arrangement of $h_1,\ldots,h_n$ (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial ...
4
This paper by Keith Ball seems to be what you are looking for:
Ball, Keith. "Isometric embedding in $\ell_p$-spaces."
European Journal of Combinatorics 11.4 (1990): 305-311.
Link to the paper here:
https://www.sciencedirect.com/science/article/pii/S019566981380131X
4
(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few.
Might it be the case that a RAM program can solve general CNF-SAT in exponential time with a base less than 2, but also requiring exponential space, so that when translated to a TM the algorithm runs in exponential time with a base ...
4
There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.
3
There is a list of open problems in graph theory and combinatorics collected and maintained by Douglas B. West.
This page maintains a list of lists of open problems in parameterized complexity.
2
There's the TLCA List of Open Problems, collecting unsolved problems in $\lambda$-calculi and related areas, such as proof theory, semantics and theory of programming languages. It is maintained by Ryu Hasegawa, Luca Paolini and Paweł Urzyczyn.
There's also a related list, the RTA list of open problems, concerning rewriting theory. At some point it was ...
2
In Formal Verification game theory is a recurring theme. I think that one of the most important applications is to define the Simulation Preorder as a game between two players: Spoiler (he) and Duplicator (she). Given a Transition System (in other words, one set $S$ equipped with a labelled transition relation $S \rightarrow S$) Spoiler, starting from a ...
1
Since the title is about CS and not TCS, maybe an answer about applications of game theory to networking can be of some interest.
Questions about game theory and equilibria arise naturally in networking, since the networks that make Internet are economic competitors and belong to different companies, but they need to collaborate in order to ensure ...
Only top voted, non community-wiki answers of a minimum length are eligible
