수학 채널 알림 알림 중 알림 취소 구독 구독 중 구독 취소 구독자 2299명 알림수신 53명 @시스티나 각종 수학 이야기를 해는 채널 질문 어떤 명제를 증명하는 것에 대한 알고리즘이 존재할까? ㅇㅇ 추천 1 비추천 0 댓글 3 조회수 337 작성일 2023-08-27 07:33:52 ⚠️ 이 게시물은 작성자가 삭제할 수 없도록 설정되어 있습니다. https://arca.live/b/math/84782942 그 알고리즘의 시간복잡도는 무엇일까? 추천! 1 ( 0) 비추! 0 ( 0) 공유 댓글 [3] 글쓰기 Specificity 2023-08-27 07:55:09 답글 1차 술어 논리만 해도 결정불가능하다고 합니다. 결정불가능이라는 건 그런 걸 알 수 있는 일반적인 알고리즘이 없다는 말입니다. 펼쳐보기▼ Specificity 2023-08-27 07:57:02 답글 명제논리의 경우에는 충족가능성(sat) 문제가 있습니다. https://en.m.wikipedia.org/wiki/Boolean_satisfiability_problem 2SAT까지는 선형시간으로 가능하지만, 3SAT부터는 NP완전이고, 지수시간 알고리즘만 있습니다. Wikimedia Foundation, Inc. Boolean satisfiability problem - Wikipedia 명제논리의 경우에는 충족가능성(sat) 문제가 있습니다. https://en.m.wikipedia.org/wiki/Boolean_satisfiability_problem 2SAT까지는 선형시간으로 가능하지만, 3SAT부터는 NP완전이고, 지수시간 알고리즘만 있습니다. 펼쳐보기▼ 정규식 2023-09-01 16:23:24 답글 사람은 빨리 증명을 해내는게 왜 가능한걸까 펼쳐보기▼ 새로운 댓글이 달렸습니다! 댓글 작성 음성댓글 아카콘 업로드 중 0초 해당 브라우저에서는 오디오 플레이어를 지원하지 않습니다. 녹음 중지 삭제 업로드 작성 글쓰기 전체글 개념글 등록순 추천순 (24시간) 추천순 (3일) 추천순 (전체) 댓글갯수순 (3일) 최근댓글순 추천컷 5 10 20 30 50 70 100 기타 최근 최근 방문 채널 최근 방문 채널 모두 삭제 전체 수학 정보 공지·운영 질문 교육 정보 유머 간단한 문제 정답/풀이 답변 운영 대회 번호 제목 작성자 작성일 조회수 추천 보통 석사과정에서 요구되는 미분적분학은 뭘로 공부 해야함? [2] ㅇㅇ 2023.08.31 427 0 질문 수학철학이 수학에 필요함? [13] 왜이렇게빨리끝내나요아리스 2023.08.30 548 -2 질문 극한의 용어 관련 질문 [3] 파라과이등골 2023.08.30 371 0 수학의 분류 이과지망생 2023.08.29 242 4 풍요 속의 빈곤-6차 1 [7] wertox 2023.08.29 565 5 질문 d-dim 힐베르트 공간이랑 슈미트 분해 배우려면 무슨 과목을 봐야 하나요? [1] ㅇㅇ (210.218) 2023.08.29 253 1 항하사, 아승기, 나유타, 불가사의, 무량대수 <- 이거 전부 불교 용어에서 유래한 표현이라고 하는데 [5] 서귀포법환포구 2023.08.29 607 0 근데 바나흐-타르스키 역설은 꼭 구에만 적용되는거임? NKPO 2023.08.29 281 0 질문 실수 질문 [9] msmtk (210.95) 2023.08.28 311 0 간단한 문제 지수법칙 이용하라는데 [2] 쿄야마카즈사와귀여운빵디부 2023.08.28 411 0 질문 부등식 질문 [1] ㅇㅇ (121.168) 2023.08.28 229 0 질문 책 추천 JOP 2023.08.28 205 1 사실 예수님은 위상수학자였다 [1] 왜이렇게빨리끝내나요아리스 2023.08.28 315 2 학교에서 책 사준다는데 추천 부탁드립니다 [5] illusion 2023.08.27 427 2 유머 님들 제가 지구 자원문제 해결하는법 알아냄 ㄷㄷㄷㄷ [10] 왜이렇게빨리끝내나요아리스 2023.08.27 1515 24 질문 어떤 명제를 증명하는 것에 대한 알고리즘이 존재할까? [3] ㅇㅇ 2023.08.27 337 1 혹시 변동확률 평균 구하는 법 물어봐도 됨? [3] ㅇㅇ 2023.08.27 348 0 질문 반정다면체 질문 [3] Kcinh 2023.08.26 228 0 dy/dx랑 비슷하게 생겼는데 d에 다른 기호 달린 거 [3] ㅇㅇ (58.122) 2023.08.26 327 0 유머 Pi는 포켓몬스터 게임을 클리어 할수 있을까? [5] 왜이렇게빨리끝내나요아리스 2023.08.26 421 2 수학 정보 ebs에서 하는 위대한 수업에서 [9] ㅇㅇ (203.246) 2023.08.26 1283 19 전개도의 개수 [14] 이과지망생 2023.08.25 1963 10 질문 수학과는 대학 이름값이 중요하나요? [12] ㅇㅇ 2023.08.25 609 3 질문 위수 n인 군 [3] ㅇㅇ 2023.08.24 306 1 질문 (a, a) = (a, a, a) [42] 14 2023.08.24 515 0 넓이는 수학적으로 어떻게 정의되나요? [2] 왜이렇게빨리끝내나요아리스 2023.08.24 334 0 질문 PMA(Rudin)난이도 [1] ㅇㅇ 2023.08.23 465 0 간단한 문제 수열문제 [2] illusion 2023.08.23 599 0 질문 정칙성 공리 질문! [9] 14 2023.08.23 435 3 질문 초딩때 생각했던 방법 [7] 아이언돔 2023.08.23 1044 6 글쓰기 전체글 개념글 등록순 추천순 (24시간) 추천순 (3일) 추천순 (전체) 댓글갯수순 (3일) 최근댓글순 추천컷 5 10 20 30 50 70 100 기타 전체 제목/내용 제목 내용 글쓴이 댓글 Keyword search form input 검색 -4 -3 -2 -1 23-08-31 06:25 +1 +2 +3 +4