stanford-oval/wikipedia huggingface dataset:
Vương quốc Bulgaria
Những năm liên tiếp > Nhân khẩu học

Vì dân số là 85% dân tộc Bulgari, có rất ít xung đột xã hội ngoài cuộc xung đột giữa những người haves và những người không có. Hầu hết cư dân của Sofia duy trì mối quan hệ chặt chẽ với nông thôn, nhưng điều này không ngăn cản sự rạn nứt giữa nông dân và tầng lớp đô thị (tức là Sofia so với mọi người khác), mặc dù một số là kết quả của việc thao túng cố ý của các chính trị gia tìm cách tận dụng lợi thế của người nông dân truyền thống của "slicker thành phố effeminate". Tuy nhiên, chủ yếu là do một cuộc cãi vã giữa những người cai trị và cai trị. Khoảng 14% dân số là người Hồi giáo, chủ yếu là người Thổ Nhĩ Kỳ (tức là phần còn lại của tầng lớp đất đai), nhưng cũng có một số ít được gọi là "Pomaks" (người Bulgaria thực hành Hồi giáo). Dân số Hồi giáo đã xa lánh với các Kitô hữu chính thống thống trị cả vì lý do tôn giáo và lịch sử. Họ không ép cho quyền thiểu số cũng không cố gắng thiết lập trường học của riêng họ, và thay vào đó không yêu cầu gì hơn là để lại một mình để tâm trí kinh doanh riêng của họ. Chính phủ Bulgaria có nghĩa vụ ngoại trừ một sự sẵn sàng lớn để hỗ trợ họ di cư trở lại Thổ Nhĩ Kỳ.
So với kinh tế học, hệ thống giáo dục của Bulgaria rất thành công và chưa đến một nửa dân số mù chữ. Tám năm học được yêu cầu và hơn 80% trẻ em tham dự. Đối với một số học sinh đặc biệt đã học tiểu học, các trường trung học được dựa trên phòng tập thể dục của Đức. Các kỳ thi cạnh tranh được sử dụng để đánh giá ứng viên đại học, và Bulgaria có một số trường kỹ thuật và chuyên ngành ngoài Đại học Sofia. Nhiều sinh viên Bulgaria cũng đã đi ra nước ngoài, chủ yếu đến Đức và Áo (quan hệ giáo dục với Nga kết thúc vào năm 1917). Nhìn chung, giáo dục đạt được nhiều tầng lớp thấp hơn bất cứ nơi nào khác ở Đông Âu, nhưng mặt khác, tất cả các sinh viên đều có bằng cấp về nghệ thuật tự do và các môn trừu tượng khác và không thể tìm được việc ở bất cứ đâu ngoại trừ trong bộ máy quan liêu của chính phủ. Nhiều người trong số họ bị cuốn hút về phía Đảng Cộng sản Bulgaria.
Cuộc đảo chính cộng sản

Mặt trận Tổ quốc đã nhậm chức tại Sofia sau một cuộc đảo chính, thiết lập một liên minh rộng lớn dưới thời cựu lãnh đạo Kimon Georgiev và bao gồm cả đảng Dân chủ Xã hội và Nông dân. Theo các điều khoản của hòa giải hòa bình, Bulgaria được phép giữ miền Nam Dobruja, nhưng chính thức từ bỏ tất cả các tuyên bố lãnh thổ Hy Lạp và Nam Tư. 150.000 người Bulgaria bị trục xuất khỏi Hy Lạp Thrace. Những người cộng sản cố ý lấy một vai trò nhỏ trong chính phủ mới lúc đầu, nhưng các đại diện của Liên Xô là lực lượng thực sự trong nước. Một dân quân do Cộng sản kiểm soát được thành lập, điều này đã quấy rầy và đe dọa các đảng không phải của Đảng Cộng sản.
Vào ngày 1 tháng 2 năm 1945, những thực tế quyền lực mới ở Bulgaria được thể hiện khi Nhiếp chính hoàng Kiril, cựu thủ tướng Bogdan Filov, và hàng trăm quan chức cũ của chế độ cũ đã bị bắt vì tội ác chiến tranh. Vào tháng Sáu, Kirill và các Cơ quan khác, hai mươi hai cựu bộ trưởng, và nhiều người khác đã bị hành quyết. Vào tháng 9 năm 1946, chế độ quân chủ đã bị bãi bỏ bởi plebiscite, và Tsar Simeon trẻ đã bị đày đi. Cộng sản bây giờ công khai nắm quyền, với Vasil Kolarov trở thành Tổng thống và Dimitrov trở thành Thủ tướng. Cuộc bầu cử tự do hứa hẹn cho năm 1946được blatantly gian lận và đã bị tẩy chay bởi phe đối lập. Người nông dân từ chối hợp tác với chế độ mới, vào tháng 6 năm 1947, thủ lĩnh Nikola Petkov của họ đã bị bắt. Bất chấp những cuộc biểu tình quốc tế mạnh mẽ, ông đã bị hành quyết vào tháng Chín. Điều này đánh dấu sự thành lập cuối cùng của một chế độ Cộng sản ở Bulgaria.
Ferdinand I của Bulgaria trong tuyên bố độc lập của Bulgaria, 1908
Ranh giới trên vùng Balkan sau Chiến tranh Balkan lần thứ nhất và thứ hai (1912-1913)
Các khu vực mà Người Bulgaria gốc là phần lớn dân số (màu xanh lục nhạt) vào năm 1912
Các sĩ quan Bulgaria trên Mặt trận Macedonia
Lãnh thổ lớn nhất của Vương quốc Bulgaria (1915-18) trong Thế chiến I (bao gồm cả lãnh thổ bị chiếm đóng)
Boris III của Bulgaria trị vì từ 1918 đến 1943
Aleksandar Stamboliyski
Aleksandar Tsankov
Georgi Kyoseivanov
Cô gái nông dân Bulgaria trong thập niên 1930
Đại học Sofia năm 1935
Quân đội Bulgaria
Bulgaria trong Thế chiến II
Danh sách quân chủ Toscana

Dưới đây là danh sách những người cai trị xứ Toscana từ khi còn là một phiên hầu quốc của Đế quốc La Mã Thần thánh cho đến hiện tại.
Phiên hầu quốc Toscana (812 -1197) > Nhà Boniface (812 - 931)

Boniface I (812 - 813).
Boniface II (828 - 834).
Aganus (835 - 845).
Adalbert I (847 - 866).
Adalbert II (886 - 915).
Guy (915 - 920).
Lambert (929 - 931).
Phiên hầu quốc Toscana (812 -1197) > Nhà Boso (931 - 1001)

Họ là những người con ngoài dã thú của Hugh của Ý,vua của Ý được bổ nhiệm sau khi ông này xóa bỏ sự hiện diện của nhà Boniface trên vùng đất này.
Boso (931 - 936).
Humbert (936 - 961).
Hugh Vĩ đại (961 - 1001).
Phiên hầu quốc Toscana (812 -1197) > Nhà Hucpold (1004 - 1011)

Boniface (III), (1004 - 1011).
Phiên hầu quốc Toscana (812 -1197) > Không triều đại (1014 - 1027)

Rainier (1014–1027).
Phiên hầu quốc Toscana (812 -1197) > Nhà Canossa (1027 - 1115)

Những người được liệt kê dưới đây là hâu duệ của Bá tước nhà Canossa.
Boniface III (1027–1052), còn được gọi với cái tên khác là Boniface IV hay Boniface nhà Canossa.
Boniface IV Frederick (1052 - 1055).
Matilda (1052 - 1115), đôi khi còn được gọi là la Gran Contessa ("Nữ Công tước Vĩ đại") hay Matilda nhà Canossa .
Beatrice của Bar (1052 - 1055), nhiếp chính của Boniface IV Frederick và Matilda với tư cách là mẹ.
Godfrey III Kẻ có râu (1053 - 1069), nhiếp chính phiên quốc với tư cách là chồng của Beatrice và cha dượng của 2 người com Boniface IV Frederick và Matilda.
Godfrey IV Kẻ lưng gù (1069 - 1076), nhiếp chính với tư cách là chồng của Matilda.
Welf II Kẻ mập (1089–1095), đồng nhiếp chính với tư cách là chồng của Matilda.
Phiên hầu quốc Toscana (812 -1197) > Không triều đại

Rabodo (1116 - 1119), còn có tên khác là Rapoto.
Conrad (1119/1120 - 1129/1131).
Rampret (khoảng 1131).
Engelbert (1135 - 1137).
Henry Kẻ tự hào (1137 - 1139).
Ulrich nhà Attems (1139–1152), cha xứ đế quốc.
Welf VI (1152 - 1162).
Welf VII (1160 - 1167).
Rainald xứ Dassel, Tổng giám mục xứ Cologne (1160 - 1063), cha xứ đế quốc.
Christian von Buch, Tổng giám mục của Mainz (1163 - 1173), cha xứ đế quốc.
Welf VI (1167 - 1173).
Philip xứ Schwaben (1195 -1197).
Năm 1197 Philip được bầu làm vua của Đức và là người đứng đầu liên minh Toscan gồm các quý tộc, giám mục và các thị dân của xứ Toscana (dưới sự hỗ trợ của Giáo hoàng).
Frederick của Antioch (1246 - 1250), cha xứ đế quốc.
Sau đó, Toscana bị chia cắt do sự cạnh tranh của các nước cộng hòa nhỏ như Firenze, Pisa, Siena, Arezzo, Pistoia và Lucca. Đến thế kỷ 14, Firenze có được thêm lãnh thổ các nước cộng hòa nhỏ khác: lãnh thổ trên đất của phiên trấn quốc Toscana cũ như Pistoia (bị chinh phục năm 1306, chính thức sát nhập năm 1530), Arrenzo (1384), Pisa (1406) và Siena (1559). Chỉ còn duy nhất Lucca còn được độc lập cho đến thời kỳ Napoleon vào thế kỷ 19.
Người Firenze kiểm soát (1434 - 1569) > Người đứng đầu de facto (trên thực tế) của nhà Medici (1434 -1494) (tức Lãnh chúa Florence)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Cosimo de' Medici |  | 27 tháng 9 năm 1389 - 1 tháng 8 năm 1464 (75 tuổi) | 6 tháng 10 năm 1434 - 1 tháng 8 năm 1464 | Bá tước de facto đầu tiên của nhà Medici |
| Piero I Người bị gút |  | 19 tháng 9 năm 1416 - 2 tháng 10 năm 1469 (53 tuổi) | 1 tháng 8 năm 1464 - 2 tháng 12 năm 1469 | Con của Cosimo |
| Lorenzo I Vĩ đại |  | 1 tháng 1 năm 1449 - 8 tháng 4 năm 1492 (43 tuổi) | 2 tháng 9 năm 1469 - 8 tháng 4 năm 1492 | Con của Piero. |
| Giuliano I de' Medici |  | 25 tháng 3 năm 1453 - 26 tháng 4 năm 1478 (25 tuổi) | 2 tháng 9 năm 1469 - 26 tháng 4 năm 1678. | Em trai và cũng là đồng nhiếp chính của Lorenzo, bị ám sát. Con trai duy nhất của ông sau này sẽ trở thành Giáo hoàng Clemenent VII. |
| Piero II kẻ không may mắn |  | 15 tháng 2 năm 1472 - 28 tháng 12 năm 1503 (31 tuổi) | 9 tháng 4 năm 1492 - 9 tháng 11 năm 1494 | Con trai Lorenzo Vĩ đại, bị phế truất và lưu đày |
Người Firenze kiểm soát (1434 - 1569) > Cộng hòa Florence (1494-1512)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Girolamo Savonarola |  | 21 tháng 9 năm 1452 - 23 tháng 5 năm 1498 (45 tuổi) | 8 tháng 11 năm 1494 - 23 tháng 5 năm 1498. | Nhà cải cách lớn của Florence. Bị treo cổ và thiêu sống giữa quảng trường của thành phố. |
| Piero Soderini |  | 17 tháng 3 năm 1451 - 13 tháng 6 năm 1522 (71 tuổi) | 22 tháng 9 năm 1502 - 31 tháng 8 năm 1512 | Tự mình tuyên bố là nhà lãnh đạo tối cao, bị buộc phải rời khỏi Florence sau chiến dịch của nhà Medici. |
Người Firenze kiểm soát (1434 - 1569) > Nhà Medici tái cầm quyền (1512 - 1532)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Note |
| --- | --- | --- | --- | --- |
| Giovanni di Lorenzo de' Medici |  | 11 tháng 12 năm 1475 - 1 tháng 12 năm 1521 (45 tuổi) | 14 tháng 9 năm 1512 - 9 tháng 3 năm 1513 | Con trai Loreno Vĩ đại, sau này trở thành Giáo hoàng Lêô X |
| Giuliano II, Công tước xứ Nermours |  | 12 tháng 3 năm 1479 - 11 tháng 3 năm 1516 (37 tuổi) | 9 tháng 3 năm 1513 - 17 tháng 3 năm 1516 | Son of Lorenzo |
| Lorenzo II de' Medici |  | 12 tháng 4 năm 1492 - 4 tháng 5 năm 1519 (26 tuổi) | 17 tháng 3 năm 1516 - 4 tháng 5 năm 1519. | Con trai của Piero II. Ông cũng đồng thời giữ chức Công tước xứ Urbino trong cùng khoảng thời gian trên. |
| Đức hồng y Giulio de' Medici |  | 26 tháng 5 năm 1478 - 25 tháng 9 năm 1534  (56 tuổi) | 4 tháng 5 năm 1519 - 19 tháng 11 năm 1523 | Con của Giuliano I de' Medici, sau là giáo hoàng Clemete VII |
| Ippolito de' Medici |  | 15 tháng 3 năm 1511 - 10 tháng 8 năm 1535 (24 tuổi) | 19 tháng 11 năm 1523 - 16 tháng 5 năm 1527 | Con trai của Giuliano I de Medici. |
| Alessandro de' Medici "Người Moor" |  | 22 tháng 7 năm 1510 - 6 tháng 1 năm 1537 (26 tuổi) | 16 tháng 5 năm 1527 - 1530 (lần 1) và 5 tháng 7 năm 1531 - 5 tháng 4 năm 1432 (lần 2) | Con trai của Lorenzo II de' Medici, cai trị trong cảnh lưu vong. Sau này trở thành Công tước xứ Florence và bị ám sát. |
Công tước (nhà Medici) của xứ Florence (1532 - 1569)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Alessandro de' Medici "Người Moor" |  | 22 tháng 7 năm 1510 - 6 tháng 1 năm 1537 (26 tuổi) | 5 tháng 4 năm 1532 - 6 tháng 1 năm 1537 | Con trai của Lorenzo II de' Medici, cai trị trong cảnh lưu vong. Sau này trở thành Công tước xứ Florence và bị ám sát. |
| Cosimo I de' Medici |  | 12 tháng 6 năm 1519 - 21 tháng 4 năm 1574 (54 tuổi) | 6 tháng 1 năm 1537 - 21 tháng 8 năm 1569 | Con của Giovanni dalle Bande Nere, sau trở thành Đại Công tước đầu tiên của xứ Toscana. |
Đại Công tước xứ Toscana (nhà Medici, 1569 - 1737)

| Tên | Chân dung | Năm sinh- năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Cosimo I de' Medici |  | 12 tháng 6 năm 1519 - 21 tháng 4 năm 1574 (54 tuổi) | 21 tháng 8 năm 1569 - 21 tháng 4 năm 1574 | Con của Giovanni dalle Bande Nere, sau trở thành Đại Công tước đầu tiên của xứ Toscana. |
| Francesco I de' Medici |  | 25 tháng 3 năm 1541 - 19 tháng 10 năm 1587 (46 tuổi) | 27 tháng 4 năm 1574 - 17 tháng 10 năm 1587 | Con của Cosimo I de' Medici. |
| Ferdinando I de' Medici |  | 30 tháng 7 năm 1549 - 3 tháng 2 năm 1609 (59 tuổi) | 19 tháng 10 năm 1587 - 7 tháng 2 năm 1609 | Con trai của Cosimo I. |
| Cosimo II de' Medici |  | 12 tháng 5 năm 1590 - 28 tháng 2 năm 1621 (30 tuổi) | 17 tháng 2 năm 1609 - 28 tháng 2 năm 1621 | Con của Ferdinando I de' Medici |
| Ferdinando II de' Medici |  | 14 tháng 7 năm 1610 - 23 tháng 5 năm 1670 (59 tuổi) | 28 tháng 2 năm 1621 - 23 tháng 5 năm 1670. | Con cả của Cosimo II de' Medici. |
| Cosimo III de' Medici |  | 14 tháng 8 năm 1642 - 31 tháng 10 năm 1723 (81 tuổi) | 23 tháng 5 năm 1670 - 31 tháng 10 năm 1723 | Con của Ferdinando II de' Medici. |
| Gian Gastone de' Medici |  | 24 tháng 5 năm 1671 - 9 tháng 7 năm 1737 (66 tuổi) | 31 tháng 10 năm 1723 - 9 tháng 7 năm 1737 | Con của Cosimo III de' Medici. Đại Công tước cuối cùng của nhà Medici thống trị xứ Toscana. |
Đại Công tước xứ Toscana (nhà Habsburg-Lothringen, 1737 - 1801)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Francesco II Stefano |  | 8 tháng 12 năm 1708 - 18 tháng 8 năm 1765 (56 tuổi) | 12 tháng 7 năm 1737 - 18 tháng 8 năm 1765 | Cháu nội 3 đời của Francesco I de' Medici. Sau này ông sẽ trở thành Hoàng đế La Mã Thần thánh. |
| Pietro Leopoldo I |  | 5 tháng 5 năm 1747 - 1 tháng 3 năm 1792 (44 tuổi) | 18 tháng 8 năm 1765 - 22 tháng 7 năm 1790 | Con trai thứ hai của Francesco II. Sau này ông sẽ trở thành Hoàng đế La Mã Thần thánh. |
| Ferdinando III |  | 6 tháng 5 năm 1769 - 18 tháng 6 năm 1824 (55 tuổi) | 22 tháng 7 năm 1790 - 3 tháng 8 năm 1801. | Con trai thứ hai của Leopoldo I. |
Vua nhà Bourbon-Parma của xứ Etruria (Vương quốc Etruria, 1801 - 1807)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Lodovico I |  | 5 tháng 7 năm 1773 - 27 tháng 5 năm 1803 (29 tuổi) | 21 tháng 3 năm 1801 - 27 tháng 5 năm 1803 | Cháu của Francisco II Stefano. |
| Lodovico II |  | 22 tháng 12 năm 1799 - 16 tháng 4 năm 1883 (83 tuổi) | 27 tháng 5 năm 1803 - 10 tháng 12 năm 1807 | Con trai của Lodovico I |
Sau khi bị sát nhập vào năm 1807, người chị Elisa Bonaparte của Napoleon giữ chức Nữ Đại Công tước xứ Tuscany (danh dự) cho đến năm 1814, nhưng bà không bao giờ kiểm soát hoàn toàn được vùng này.
Nhà Habsburg-Lothringen tái cai trị Toscana (1814 - 1860)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian cai trị | Ghi chú |
| --- | --- | --- | --- | --- |
| Ferdinando III |  | 6 tháng 5 năm 1769 - 18 tháng 6 năm 1824 (55 tuổi) | 27 tháng 4 năm 1814 - 18 tháng 6 năm 1824 | Tái khôi phục chức vị. |
| Leopoldo II |  | 3 tháng 10 năm 1797 - 21 tháng 7 năm 1859 (72 tuổi) | 18 tháng 6 năm 1824 - 21 tháng 7 năm 1859 | Con trai Ferdinando III |
| Ferdinando IV |  | 10 tháng 6 năm 1835 - 17 tháng 1 năm 1908 (72 tuổi) | 21 tháng 7 năm 1859 - 22 tháng 3 năm 1860 | Con trai Leopoldo II |
Sau khi bị buộc phải rời khỏi xứ Tuscany vào các năm 1849 và 1859, Leopoldo II nhường ngôi cho con mình là Ferdinando IV vào ngày 21 tháng 7 năm 1859. Tuy vậy, ông này không được chính quyền lâm thời mới ở Toscana công nhận và bị phế truất vào ngày 16 tháng 8. Toscana sau này sẽ sát nhập với vương quốc Sardinia vào ngày 22 tháng 3 năm 1860.
Nhánh trưởng nhà Habsburg-Toscana (1860 - nay, tự tuyên bố là Đại Công tước xứ Toscana)

| Tên | Chân dung | Năm sinh - năm mất | Thời gian giữ tước hiệu |
| --- | --- | --- | --- |
| Ferdinando IV |  | 10 tháng 6 năm 1835 - 17 tháng 1 năm 1908 (72 tuổi) | 22 tháng 3 năm 1860 - 17 tháng 1 năm 1908 |
| Giuseppe Ferdinando |  | 24 tháng 5 năm 1872 - 28 tháng 8 năm 1942 (70 tuổi) | 17 tháng 1 năm 1908 - 2 tháng 5 năm 1921 |
| Pietro Ferdinando |  | 12 tháng 5 năm 1874 - 8 tháng 11 năm 1948 (74 tuổi) | 2 tháng 5 năm 1921 - 8 tháng 11 năm 1948 |
| Goffredo |  | 14 tháng 3 năm 1902 - 21 tháng 1 năm 1984 (81 tuổi) | 8 tháng 11 năm 1948 - 21 tháng 1 năm 1984 |
| Leopoldo Francesco |  | 25 tháng 10 năm 1942 - nay. (77 tuổi) | 21 tháng 1 năm 1984 - 18 tháng 6 năm 1993 |
| Sigismondo |  | 21 tháng 4 năm 1966 - nay. (64 tuổi) | 18 tháng 6 năm 1993 - nay. |
Myiophobus inornatus

| Myiophobus inornatus> Phân loại khoa học |
| --- | --- |
Giới (regnum): Animalia
Ngành (phylum): Chordata
Lớp (class): Aves
Bộ (ordo): Passeriformes
Họ (familia): Tyrannidae
Chi (genus): Myiophobus
Loài (species): M. inornatus
Danh pháp hai phần
Myiophobus inornatus
Myiophobus inornatus là một loài chim trong họ Tyrannidae.
Chú thích

↑  Clements, J. F.; Schulenberg, T. S.; Iliff, M. J.; Wood, C. L.; Roberson, D.; Sullivan, B.L. (2012). “The eBird/Clements checklist of birds of the world: Version 6.7”. Truy cập ngày 19 tháng 12 năm 2012.
Xanthophyllum purpureum

| Xanthophyllum purpureum> Phân loại khoa học |
| --- | --- |
Giới (regnum): Plantae
(không phân hạng): Angiospermae
(không phân hạng): Eudicots
Bộ (ordo): Fabales
Họ (familia): Polygalaceae
Chi (genus): Xanthophyllum
Loài (species): X. purpureum
Danh pháp hai phần
Xanthophyllum purpureum Ridl., 1938 
Xanthophyllum purpureum là một loài thực vật có hoa trong họ Polygalaceae. Loài này được Ridl. miêu tả khoa học đầu tiên năm 1938.
Chú thích

↑  The Plant List (2010). “Xanthophyllum purpureum”. Truy cập ngày 17 tháng 9 năm 2013.
Lý thuyết độ phức tạp tính toán

Lý thuyết độ phức tạp tính toán (tiếng Anh: computational complexity theory) là một nhánh của lý thuyết tính toán trong lý thuyết khoa học máy tính và toán học tập trung vào phân loại các vấn đề tính toán theo độ khó nội tại của chúng. Ở đây, một vấn đề tính toán được hiểu là một vấn đề có thể giải được bằng máy tính (nói chung có nghĩa là vấn đề có thể được diễn đạt dưới dạng toán học). Một vấn đề tính toán có thể hiểu là một tập các trường hợp và lời giải cho các trường hợp đó. Ví dụ như kiểm tra tính nguyên tố là vấn đề xác định xem một số cho trước có phải số nguyên tố hay không. Mỗi trường hợp của vấn đề là một số tự nhiên, và lời giải cho mỗi trường hợp là có hoặc không tùy theo số đó có là nguyên tố hay không.
Một vấn đề được coi là khó nếu lời giải của nó đòi hỏi nhiều tài nguyên, bất kể sử dụng thuật toán nào. Lý thuyết độ phức tạp tính toán chuyển ý tưởng trực quan này thành mệnh đề toán học chặt chẽ, bằng cách đưa ra các mô hình tính toán để nghiên cứu các vấn đề này và tính lượng tài nguyên cần thiết để giải quyết chúng, chẳng hạn như thời gian hay bộ nhớ. Ngoài ra còn có những tài nguyên khác cũng được sử dụng, chẳng hạn như lượng thông tin liên lạc (dùng trong độ phức tạp truyền thông), số lượng cổng logic trong mạch (dùng trong độ phức tạp mạch) và số lượng bộ xử lý (dùng trong tính toán song song). Một trong những nhiệm vụ của lý thuyết độ phức tạp tính toán là xác định các giới hạn của những gì máy tính có thể làm và không thể làm.
Hai ngành khác trong lý thuyết khoa học máy tính có liên hệ chặt chẽ với độ phức tạp tính toán là phân tích thuật toán và lý thuyết khả tính. Điểm khác biệt mấu chốt giữa phân tích thuật toán và lý thuyết độ phức tạp tính toán là ngành thứ nhất tập trung vào phân tích lượng tài nguyên cần thiết cho một thuật toán nhất định, trong khi ngành thứ hai nghiên cứu các câu hỏi về tất cả các thuật toán có thể dùng để giải quyết vấn đề. Cụ thể hơn, nó tìm cách phân loại các vấn đề theo lượng tài nguyên cần thiết để giải quyết chúng. Việc giới hạn lượng tài nguyên là điểm khác biệt giữa độ phức tạp tính toán và lý thuyết khả tính: lý thuyết khả tính nghiên cứu xem những vấn đề nào có thể giải được về mặt nguyên tắc, mà không giới hạn tài nguyên.
Vấn đề (bài toán) tính toán > Trường hợp

Một vấn đề tính toán có thể xem là một tập vô hạn các trường hợp cùng với lời giải cho mỗi trường hợp. Không nên nhầm lẫn giữa dữ liệu vào cho mỗi vấn đề tính toán, còn gọi là một trường hợp, và bản thân vấn đề. Trong lý thuyết độ phức tạp tính toán, một vấn đề là một câu hỏi trừu tượng cần giải quyết. Một trường hợp là một trường hợp cụ thể của câu hỏi trừu tượng đó. Để rõ hơn, ta xem xét vấn đề kiểm tra tính nguyên tố. Một trường hợp là một số nguyên (ví dụ như 15) và lời giải là "có" nếu như số đó là nguyên tố và "không" nếu nó không là nguyên tố (trong trường hợp này, lời giải là "không").
Vấn đề (bài toán) tính toán > Biểu diễn trường hợp

Khi xem xét các vấn đề tính toán, một trường hợp là một xâu ký tự trong một bảng chữ cái nhất định. Bảng chữ cái thường dùng là bảng chữ cái nhị phân (gồm 2 ký tự 0 và 1). Cũng như trong máy tính trên thực tế, các đối tượng toán học cần phải được mã hóa hợp lý dưới dạng các dãy bit. Ví dụ như một số nguyên cần phải được biểu diễn dưới dạng nhị phân, đồ thị có thể được biểu diễn dưới dạng ma trận kề, hoặc mã hóa danh sách kề dưới dạng nhị phân.
Mặc dù một số chứng minh của các định lý trong lý thuyết độ phức tạp tính toán giả sử một mã hóa nhất định của dữ liệu vào, người ta thường cố gắng giữ cho các lập luận đủ trừu tượng để không phụ thuộc vào cách mã hóa. Điều này có thể đạt được bằng cách đảm bảo có thể được chuyển từ cách mã hóa này sang cách mã hóa khác một cách hiệu quả.
Vấn đề (bài toán) tính toán > Bài toán quyết định dưới dạng ngôn ngữ hình thức

Bài toán quyết định là một trong những đối tượng trọng tâm nghiên cứu của lý thuyết độ phức tạp tính toán. Một bài toán quyết định là một trường hợp đặc biệt của bài toán tính toán, với câu trả lời là có hoặc không, hay nói cách khác là 0 hoặc 1. Một bài toán quyết định có thể được xem là một ngôn ngữ hình thức, trong đó các xâu ký tự thành viên của ngôn ngữ là các những trường hợp có câu trả lời là có, các xâu ký tự không là thành viên là những trường hợp có câu trả lời là không. Mục tiêu của bài toán là sử dụng một thuật toán để quyết định xem một xâu cho trước có là thành viên của ngôn ngữ hình thức đang xem xét hay không. Nếu thuật toán quyết định là có, thì ta nói thuật toán chấp nhận xâu dữ liệu vào, nếu không thì ta nói thuật toán từ chối xâu dữ liệu vào.
Một ví dụ của bài toán quyết định là như sau. Dữ liệu vào là một đồ thị bất kì. Bài toán yêu cầu quyết định xem đồ thị có liên thông hay không. Ngôn ngữ hình thức tương ứng cho bài toán này là tập tất cả các đồ thị liên thông. Dĩ nhiên để định nghĩa chặt chẽ bài toán, cần phải quyết định xem đồ thị được mã hóa như thế nào dưới dạng xâu nhị phân.
Vấn đề (bài toán) tính toán > Bài toán hàm

Một bài toán hàm là một bài toán tính toán trong đó mỗi dữ liệu vào cho đúng một kết quả, nhưng kết quả đó phức tạp hơn kết quả của bài toán quyết định, nghĩa là nó không chỉ là có hay không. Ví dụ như bài toán người bán hàng, và bài toán phân tích ra thừa số nguyên tố.
Thoạt nhìn có vẻ khái niệm bài toán hàm là rộng hơn khái niệm bài toán tính toán. Tuy nhiên, điều này không hẳn là đúng do các bài toán hàm có thể được viết lại dưới dạng bài toán quyết định. Ví dụ như bài toán nhân hai số nguyên có thể được biểu diễn dưới dạng tập hợp các bộ ba (a, b, c) sao cho a × b < c. Quyết định xem liệu một bộ ba cho trước có phải là thành viên của tập hợp đó hay không tương ứng với việc nhân hai số.
Vấn đề (bài toán) tính toán > Kích thước của trường hợp

Để đánh giá độ khó của một bài toán tính toán, một thước đo phổ biến là lượng thời gian thuật toán tốt nhất cần dùng để giải nó. Tuy nhiên, thời gian cần thiết nói chung phụ thuộc vào từng trường hợp cụ thể. Trường hợp lớn hơn thường đòi hỏi nhiều thời gian hơn. Do đó thời gian cần thiết để giải quyết bài toán (hoặc bộ nhớ, hay bất kì một thông số độ phức tạp nào) là một hàm số của kích thước trường hợp. Kích thước thường được đo bằng kích thước dữ liệu vào với đơn vị bit. Lý thuyết độ phức tạp quan tâm đến hành vi của thuật toán khi kích thước dữ liệu vào tăng lên. Ví dụ như trong bài toán kiểm tra xem một đồ thị có liên thông hay không, thời gian cần thiết để kiểm tra một đồ thị kích thước 2n là bao nhiêu so với thời gian để kiểm tra đồ thị kích thước n?
Khi kích thước dữ liệu vào là n, thời gian có thể được biểu diễn dưới dạng một hàm số của n. Do thời gian cần thiết cho các trường hợp cùng kích thước có thể khác nhau, thời gian trong trường hợp xấu nhất T(n) được định nghĩa là lượng thời gian lớn nhất trong tất cả các trường hợp có kích thước n. Nếu T(n) là đa thức của n, thì ta nói thuật toán chạy thời gian đa thức.