Questions tagged [terminology]

questions about definitions, terms, and common names in theoretical computer science.

94 questions
Filter by
Sorted by
Tagged with
45 views

• 1,561
227 views

Typing relations terminology – how do I read typing relations?

I am currently trying to read up on type theory and have some quick questions on terminology. In the following rule, $$\frac{x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}$$ How ...
• 293
2k views

How can a problem be in NP, be NP-hard and not NP-complete?

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. However, in the famous paper "The ellipsoid method and its consequences in ...
• 1,166
4k views

Is propositional resolution a complete proof system?

This question is about propositional logic and all occurrences of "resolution" should be read as "propositional resolution". This question is something extremely basic but it has been bothering me ...
• 12.6k
988 views

Equivalent definitions of time constructibility

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
• 532
564 views

Why is combinational logic called so?

What is the significance of the word "combinational" in combinational logic?
701 views

Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
• 1,591
1 vote
178 views

Set of functions computable in polynomial time

I write paper and I want to distinguish between the class of decision problems which can be decided in polynomial time and the class functions which can be computed in polynomial time. The first is ...
• 513
280 views

Equivalent embeddings of a graph

I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent. Intuitively I mean by equivalent that the embeddings look the same up to ...
• 63
3k views

what does "lifting" mean?

I see in certain places "lifting computation" or "lifting" mentioned. I haven't been able to accurately define for myself what is meant by that. This usually comes up in computer science context. Any ...
• 131
540 views

• 133